Tag Archives: python

How many trailing zeros does a factorial have

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?