Problem Description

The Leetcode problem Preimage Size of Factorial Zeroes Function asks: Given a non-negative integer k, return the number of non-negative integers x such that the number of trailing zeroes in x! (x factorial) is exactly k.

In other words, for a given k, how many values of x satisfy f(x) == k where f(x) is the number of trailing zeros in x!?

• The function f(x) is non-decreasing: as x increases, f(x) increases or stays the same, but never decreases.
• Input: a single integer k (0 ≤ k ≤ 10⁹).
• Output: the count of all x such that f(x) == k.

Thought Process

The first step is to understand how trailing zeros are formed in factorials. Each trailing zero in x! comes from a factor of 10, which is produced by multiplying 2 and 5. Since there are usually more 2s than 5s, the number of 5s in the prime factorization of x! determines the number of trailing zeros.

For a given x, the number of times 5 divides x! is:
f(x) = x // 5 + x // 25 + x // 125 + ...

A brute-force approach would be to compute f(x) for every x up to a very large number, but this is inefficient for large k. Instead, we recognize that the function f(x) is non-decreasing and often "flat" (i.e., the same value for several consecutive x). So, for a given k, there may be a block of x values where f(x) == k. Our task is to count how many such x there are.

This suggests using binary search to efficiently find the range of x that map to a given k.

Solution Approach

The main idea is to use binary search to find the smallest x such that f(x) == k and the smallest x such that f(x) == k+1. The difference between these two values gives the number of x for which f(x) == k.

1. Define f(x):
   • For a given x, f(x) is the number of trailing zeroes in x!.
   • Compute it by summing x // 5, x // 25, x // 125, etc.
2. Use Binary Search:
   • To find the left boundary: the smallest x such that f(x) == k.
   • To find the right boundary: the smallest x such that f(x) == k+1.
   • The answer is right - left.
3. Why this works:
   • Because f(x) is non-decreasing, all x with f(x) == k are consecutive.
   • The range size is at most 5, because every block of 5 consecutive numbers increases the count of trailing zeros by 1.

In summary, we use binary search to efficiently find the range of x for which f(x) == k.

Example Walkthrough

Example: Let’s take k = 5.

1. Compute f(x) for x = 0, 1, ..., 30:
   • f(25) = 6
   • f(24) = 4
   • f(25) = 6
   • So, find x such that f(x) = 5.
2. Using binary search, find the smallest x where f(x) == 5 (let’s say it’s x1).
3. Find the smallest x where f(x) == 6 (let’s say it’s x2).
4. The answer is x2 - x1.
   In this case, for k = 5, the answer is 0, because there are no x for which f(x) == 5 (it jumps from 4 to 6).
5. For k = 0, f(0) = 0, f(1) = 0, f(2) = 0, f(3) = 0, f(4) = 0, f(5) = 1. So, there are 5 values (0,1,2,3,4) for which f(x) == 0.

Time and Space Complexity

• Brute-force: For each x up to a very large number (can be up to 5*k), compute f(x). This is O(N log N), which is infeasible for large k.
• Optimized (Binary Search):
  • Each binary search runs in O(log N), where N can be up to 5*k.
  • Each f(x) computation is O(log x), but since binary search only does this a few times, total time is O(log² N).
  • Space complexity is O(1) as we only use a constant number of variables.

Summary

The key insight is that the number of trailing zeros in x! increases in blocks, and for any given k, the x values with f(x) == k are consecutive and form a block of at most 5 numbers. By using binary search to find the boundaries of this block, we efficiently compute the answer even for very large k. This approach is both elegant and highly efficient compared to brute-force methods.

Code Implementation

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

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

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

class Solution {
public:
    int zeta(long long x) {
        int res = 0;
        while (x) {
            x /= 5;
            res += x;
        }
        return res;
    }
    int left_bound(int k) {
        long long lo = 0, hi = 5LL * k + 5;
        while (lo < hi) {
            long long mid = (lo + hi) / 2;
            if (zeta(mid) < k)
                lo = mid + 1;
            else
                hi = mid;
        }
        return (int)lo;
    }
    int preimageSizeFZF(int k) {
        return left_bound(k + 1) - left_bound(k);
    }
};
      

class Solution {
    private int zeta(long x) {
        int res = 0;
        while (x > 0) {
            x /= 5;
            res += x;
        }
        return res;
    }
    private int leftBound(int k) {
        long lo = 0, hi = 5L * k + 5;
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            if (zeta(mid) < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return (int)lo;
    }
    public int preimageSizeFZF(int k) {
        return leftBound(k + 1) - leftBound(k);
    }
}
      

var preimageSizeFZF = function(k) {
    function zeta(x) {
        let res = 0;
        while (x > 0) {
            x = Math.floor(x / 5);
            res += x;
        }
        return res;
    }
    function leftBound(k) {
        let lo = 0, hi = 5 * k + 5;
        while (lo < hi) {
            let mid = Math.floor((lo + hi) / 2);
            if (zeta(mid) < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
    return leftBound(k + 1) - leftBound(k);
};