LeetCode 793: Preimage Size of Factorial Zeroes Function

Problem Restatement

Define:

f(x)

as the number of trailing zeroes in:

x!

We are given an integer k.

We need to return how many integers x satisfy:

f(x) == k

This count is called the size of the preimage of k.

Input and Output

Function shape:

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        ...

Examples

Example 1:

k = 0

We compute:

Exactly five integers satisfy:

f(x) == 0

So the answer is:

5

Example 2:

k = 5

There is no integer x such that:

f(x) == 5

So the answer is:

0

First Thought: Compute Factorials

A direct idea is:

1. Compute factorials.
2. Count trailing zeroes.
3. Check which values produce exactly k.

This quickly becomes impossible because factorials grow extremely fast.

We need a mathematical property instead.

Key Insight

Trailing zeroes in x! come from factors of:

10 = 2 * 5

There are always more 2s than 5s in factorials, so the number of trailing zeroes equals the number of factors of 5.

The standard formula is:

f(x) = x // 5 + x // 25 + x // 125 + ...

For example:

f(25) = 25 // 5 + 25 // 25
      = 5 + 1
      = 6

Now observe an important property.

The function f(x) is monotonic:

But f(x) sometimes jumps.

For example:

The value 5 is skipped completely.

So some k values have no solutions.

When a solution exists, there are always exactly five consecutive values of x.

Why Exactly Five?

Suppose:

f(x) == k

Then:

f(x + 1)
f(x + 2)
f(x + 3)
f(x + 4)

usually remain the same until the next multiple of 5.

So solutions appear in blocks of five.

Therefore, the answer is only:

So we only need to check whether some x satisfies:

f(x) == k

Binary Search

Since f(x) is monotonic, we can binary search for the smallest x such that:

f(x) >= k

Call this value:

left_bound(k)

Then:

The number of integers satisfying:

f(x) == k

is:

left_bound(k + 1) - left_bound(k)

This difference is always 0 or 5.

Algorithm

Define a helper:

count_zeroes(x)

which computes trailing zeroes in x!.

Then define:

left_bound(target)

using binary search.

Finally return:

left_bound(k + 1) - left_bound(k)

Correctness

The number of trailing zeroes in x! equals the number of factors of 5 in the factorial expansion. Therefore:

f(x) = x // 5 + x // 25 + x // 125 + ...

correctly computes the trailing zero count.

The function f(x) is monotonic because increasing x adds more factors to the factorial and cannot decrease the number of trailing zeroes.

For a target k, left_bound(k) returns the smallest integer x such that:

f(x) >= k

Similarly, left_bound(k + 1) returns the smallest integer where:

f(x) >= k + 1

Therefore, every integer in the interval:

[left_bound(k), left_bound(k + 1))

satisfies:

f(x) == k

and no other integers do.

So the size of the preimage is exactly:

left_bound(k + 1) - left_bound(k)

which the algorithm returns.

Complexity

Let M be the binary search range.

A safe upper bound is:

5 * (k + 1)

because each multiple of 5 contributes at least one trailing zero.

Implementation

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def count_zeroes(x: int) -> int:
            total = 0

            while x > 0:
                x //= 5
                total += x

            return total

        def left_bound(target: int) -> int:
            left = 0
            right = 5 * (target + 1)

            while left < right:
                mid = (left + right) // 2

                if count_zeroes(mid) < target:
                    left = mid + 1
                else:
                    right = mid

            return left

        return left_bound(k + 1) - left_bound(k)

Code Explanation

The helper computes trailing zeroes:

def count_zeroes(x: int) -> int:

Each division counts how many numbers contribute extra factors of 5:

x //= 5
total += x

The binary search finds the first value where:

f(x) >= target

If the current midpoint has too few zeroes:

if count_zeroes(mid) < target:
    left = mid + 1

Otherwise, we move leftward to find the first valid position:

else:
    right = mid

Finally, the number of exact matches is:

left_bound(k + 1) - left_bound(k)

Testing

def run_tests():
    s = Solution()

    assert s.preimageSizeFZF(0) == 5
    assert s.preimageSizeFZF(1) == 5
    assert s.preimageSizeFZF(2) == 5
    assert s.preimageSizeFZF(3) == 5
    assert s.preimageSizeFZF(4) == 5

    assert s.preimageSizeFZF(5) == 0

    assert s.preimageSizeFZF(6) == 5

    assert s.preimageSizeFZF(10) == 5
    assert s.preimageSizeFZF(11) == 0

    print("all tests passed")

run_tests()

Test coverage: