Leetcode: 172. Factorial Trailing Zeroes

The simplest approach is to compute \(n!\) and then counting the leading zeros. Note that it would require a big integer to compute factorial of \(10^4!\) since it has \(35660\) digits (see more about Counting the number of digits of an integer).

Other way without use of big integers consist on Count leading zeros of a number using its 2's and 5's factors. The number of leading zeros in \(n!\) is the minimum between the number of its 2's and 5's factors.

from functools import reduce
from operator import add


class Solution:
    def trailingZeroes(self, n: int) -> int:
        def count_factors(n, f):
            ret = 0
            while n % f == 0 and n >= f:
                ret += 1
                n = n // f
            return ret

        if n == 0:
            return 0

        f2 = reduce(add, [count_factors(k, 2) for k in range(1, n + 1)])
        f5 = reduce(add, [count_factors(k, 5) for k in range(1, n + 1)])

        return min(f2, f5)


assert Solution().trailingZeroes(3) == 0
assert Solution().trailingZeroes(5) == 1
assert Solution().trailingZeroes(0) == 0