Preimage Size of Factorial Zeroes Function — LeetCode 793 Python Solution

The problem

Let f(x) be the number of zeroes at the end of x!. Recall that x!

Example

Input

k = 0

Output

5

Explanation

0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

Python solution

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def f(x):
            if x == 0:
                return 0
            return x // 5 + f(x // 5)

        def g(k):
            return bisect_left(range(5 * k), k, key=f)

        return g(k + 1) - g(k)

Complexity

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 793. Preimage Size of Factorial Zeroes Function is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems