Simple question: How many trailing zero does 10000! have?
Simple to solve it using python
import math factorial_answer = str(math.factorial(10000)) print(len(factorial_answer) - len(factorial_answer.rstrip('0')))
Python think about 100ms and tell me the answer is 2499.
This question is name as “Trailing zeros”
The question become:
So we can just integer divide 10000 by 5 and get 2000, integer divide 2000 by 5 and get 400…. and sum all answers (2000, 400, …) until get 0.
let’s using recursion
def f(r, c=0): if r == 0: return c else: return f(r // 5, c + r // 5) print(f(10000))
The function take two arguments, one for current answer, another for count result.
and make it into one line
f = lambda r, c=0: c if r == 0 else f(r // 5, c + r // 5) print(f(10000))
Here we assign lambda expression to f and invoke it recursively. However, assign lambda expression is not recommended in PEP8. 不, 这不PEP8. And function f is exposed in namespace. There are ways to make recursive into anonymous lambda function that won’t pollute namespace, as well as make it into really one line.
print((lambda a: lambda r, c = 0: a(a, r, c))(lambda s, r, c: c if r == 0 else s(s, r // 5, c + r // 5))(10000))
Another flaw is, we use same division twice, more precisely, “r // 5” twice.
To eliminate duplicate, closure may help.
def f(r): def _f(r): while r != 0: r //= 5 yield r return sum(_f(r)) print(f(10000))
The process become, constantly dividing number by 5 and yield it to sum, until zero.
Make a function for that “continuously do something and yield it, until some condition” operation
def repeat_w_func(initial_input, repeat_func=None, yield_input=False, end_func=None): """ constantly do calculate function and take output as next time input :param initial_input: the initial input :param repeat_func: the function that will be evaluate repeatedly if not set, the function behavior like itertools.repeat(initial_input) :param yield_input: if set to True, initial_input will be yield once before yielding repeat_func output :param end_func: the function that will end the loop and stop yielding. if not set, yielding will be endless :return: a generator """ result = initial_input if yield_input: yield result if repeat_func: while True: if end_func: if end_func(result): break result = repeat_func(result) yield result else: while True: yield initial_input
With brand new repeat with function function, we can solve the question elegantly, with help of itertools.takewhile function.
from itertools import takewhile print(sum(takewhile(lambda x: x != 0, repeat_w_func(10000, lambda x: x // 5))))
Solve in function programming language like Haskell.
Is there a written functional just work like the repeat_w_func function in python or package?
One thought on “How many trailing zeros does a factorial have”