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”
https://en.wikipedia.org/wiki/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))))
Future research
Solve in function programming language like Haskell.
Is there a written functional just work like the repeat_w_func function in python or package?
