Preimage Size of Factorial Zeroes Function: Binary Search on Math

May 22, 20266 min read

leetcodeproblemhardmathbinary-search

Preimage Size of Factorial Zeroes Function is LeetCode 793. Given a non-negative integer k, you need to find how many non-negative integers n exist such that n! (n factorial) has exactly k trailing zeroes.

The answer is always either 0 or 5. That sounds surprising at first, but it falls out naturally from how trailing zeroes accumulate in factorials.

Examples:

k = 0 returns 5 (n = 0, 1, 2, 3, 4 all have 0 trailing zeroes)
k = 5 returns 0 (no n produces exactly 5 trailing zeroes, because f(24) = 4 and f(25) = 6)
k = 1 returns 5 (n = 5, 6, 7, 8, 9 all produce exactly 1 trailing zero)

Each cell shows n | f(n), where f(n) counts trailing zeroes in n!. Between multiples of 5, five consecutive n values share the same f(n). At multiples of 25, f(n) jumps by 2, skipping a value of k entirely.

Why this problem matters

This problem builds directly on LeetCode 172 (Factorial Trailing Zeroes), where you learn to count trailing zeroes in n! using Legendre's formula. Here, you flip the question: instead of "given n, find f(n)," you ask "given k, how many n values satisfy f(n) = k?"

That inversion is a powerful pattern. Many hard problems take a function you already know how to compute and ask you to reason about its inverse. The technique for answering that question, binary search on a monotonic function, shows up repeatedly in competitive programming and interviews.

Understanding why the answer is always 0 or 5 also deepens your number theory intuition. It connects the structure of prime factorization to the behavior of a discrete function, and it shows that "weird" constraints on the answer often come from clean mathematical structure underneath.

The approach

Trailing zeroes in n! come from factors of 10, and since 10 = 2 * 5, the count is limited by factors of 5 (there are always more factors of 2). The trailing zero count function is:

f(n) = floor(n/5) + floor(n/25) + floor(n/125) + ...

This function is non-decreasing. As n increases, f(n) either stays the same or increases. Between consecutive multiples of 5, f(n) does not change at all. When n crosses a multiple of 5, f(n) increases by 1. When n crosses a multiple of 25, f(n) increases by 2 (one from the floor(n/5) term and one more from the floor(n/25) term). That jump of 2 means one value of k gets skipped.

Here is the full picture:

For most values of k, exactly 5 consecutive integers n all map to the same trailing zero count. These are the integers between two consecutive multiples of 5. So the answer is 5.
When n crosses a multiple of 25 (or 125, 625, etc.), f(n) jumps by 2 or more. The skipped k values have zero preimages. So the answer is 0.

The algorithm uses binary search twice (or once, depending on how you frame it). You binary search for the smallest n where f(n) >= k. Call that value n_min. If f(n_min) == k, then k is achievable, and the answer is 5. If f(n_min) > k, then k was skipped, and the answer is 0.

Practice this problem with spaced repetition

Clean solution

def preimageSizeFZF(k):
    def f(n):
        count = 0
        d = 5
        while d <= n:
            count += n // d
            d *= 5
        return count

    lo, hi = 0, 5 * (k + 1)
    while lo < hi:
        mid = (lo + hi) // 2
        if f(mid) < k:
            lo = mid + 1
        else:
            hi = mid
    return 5 if f(lo) == k else 0

Step-by-step walkthrough

Binary search to find the smallest n where f(n) >= k. Example: k = 1

Step 1: Set search range

lo =0hi =5 * (k + 1) = 10

goal:find smallest n where f(n) >= 1

The upper bound 5 * (k + 1) is always large enough because f(5k) is at least k.

Step 2: mid = 5, f(5) = 1

lo =0hi =10mid =5

f(5) =1>= k, so hi = 5

f(5) = floor(5/5) = 1, which meets our target. The answer could be 5 or smaller.

Step 3: mid = 2, f(2) = 0

lo =0hi =5mid =2

f(2) =0< k, so lo = 3

f(2) = 0 is too small. We need a larger n.

Step 4: mid = 4, f(4) = 0

lo =3hi =5mid =4

f(4) =0< k, so lo = 5

f(4) = 0 still. The jump from 0 to 1 happens exactly at n = 5.

Step 5: lo = hi = 5. Converged.

smallest n with f(n) >= 1:n = 5

f(5) =1 == k

f(5) equals k exactly, so k = 1 is achievable. The answer is 5.

Result: preimageSizeFZF(1) = 5

We found that f(5) = 1 = k, confirming k is not skipped. Since f(n) stays equal to 1 for n = 5, 6, 7, 8, 9 (five consecutive values before the next multiple of 5), the answer is 5.

The binary search narrows the range quickly because the upper bound 5 * (k + 1) is at most 5 times larger than k, so the search runs in O(log k) iterations. Each iteration computes f(mid) in O(log mid) time by dividing by successive powers of 5.

Once the search converges to n_min, you check whether f(n_min) equals k. If it does, k is a valid trailing zero count, and exactly 5 values of n produce it. If f(n_min) is larger than k, the function jumped over k, so no n produces it.

The answer is always 0 or 5. You never need to count how many n values give k trailing zeroes. You just need to know whether k is achievable or skipped. Binary search tells you that in O(log k * log k) time.

Complexity analysis

Approach	Time	Space
Binary search + trailing zero formula	O(log^2 k)	O(1)

The outer binary search runs in O(log k) iterations (the search space is proportional to k). Each iteration calls f(mid), which loops through powers of 5 up to mid, taking O(log mid) = O(log k) time. Multiplying these gives O(log^2 k). No extra data structures are needed.

Build your pattern library with CodeBricks

The building blocks

1. Trailing zeroes in factorial (Legendre's formula)

The function f(n) = floor(n/5) + floor(n/25) + floor(n/125) + ... counts how many times 5 divides n!. This is a special case of Legendre's formula, which counts how many times any prime p divides n!.

def f(n):
    count = 0
    d = 5
    while d <= n:
        count += n // d
        d *= 5
    return count

The key property you rely on here is that f is non-decreasing and only increases at multiples of 5. That monotonicity is what makes binary search valid.

2. Binary search on a monotonic function

When you have a non-decreasing function and want to find the first input where the output reaches a target, binary search is the tool. The template is:

Set lo and hi to bound the search range.
While lo < hi, compute mid and evaluate the function.
If the function value is too small, move lo up. Otherwise, move hi down.
When the loop ends, lo is the smallest input where the function reaches the target.

This is the same pattern used in Koko Eating Bananas, Kth Smallest in Multiplication Table, and many other "binary search on the answer" problems.

Edge cases to watch for

k = 0: f(0) = 0, so 0 is achievable. The answer is 5 (n = 0, 1, 2, 3, 4).
Large k: The upper bound 5 * (k + 1) keeps the search range manageable. For k up to 10^9, the binary search still runs in about 60 iterations.
Skipped values near powers of 25: f(24) = 4 and f(25) = 6, so k = 5 has no preimage. Similarly, f(124) = 28 and f(125) = 31, so k = 29 and k = 30 are both skipped.
k = 1: The smallest n with f(n) = 1 is n = 5. The values n = 5, 6, 7, 8, 9 all give f(n) = 1, so the answer is 5.

From understanding to recall

You now know why the answer is always 0 or 5, how Legendre's formula connects trailing zeroes to factors of 5, and how binary search on a monotonic function finds the boundary. The pieces fit together cleanly.

But in an interview, you need the full chain to come to mind instantly: trailing zeroes means factors of 5, the count function is monotonic, monotonic means binary search, and the jump behavior means the answer is 0 or 5. Spaced repetition turns that chain into reflex. Solve it today, again in a few days, then a week later. After a few rounds, the pattern is yours permanently.

Factorial Trailing Zeroes - The prerequisite problem: counting trailing zeroes
Binary Search - The core binary search pattern used here
Kth Smallest Number in Multiplication Table - Another binary search on a math function

Try CodeBricks free