Preimage Size of Factorial Zeroes Function
HardPrompt
Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 * 2 * 3 * ... * x and by convention, 0! = 1.
- For example,
f(3) = 0because3! = 6has no zeroes at the end, whilef(11) = 2because11! = 39916800has two zeroes at the end.
Given an integer k, return the number of non-negative integers x have the property that f(x) = k.
Example 1:
Input: k = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.Example 2:
Input: k = 5
Output: 0
Explanation: There is no x such that x! ends in k = 5 zeroes.Example 3:
Input: k = 3
Output: 5
Constraints:
0 <= k <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through non-negative integers x starting from 0. For each x, we calculate f(x), which is the number of trailing zeros in the factorial of x. We keep a count of how many times f(x) is equal to the given k. We can stop iterating once f(x) exceeds k because f(x) is a non-decreasing function.
Algorithm
- Initialize a counter
countto 0 and an integerxto 0. - Create a helper function,
countZeros(n), that computes the number of trailing zeros inn!. This is done by summingfloor(n/5) + floor(n/25) + floor(n/125) + .... - Start an infinite loop, incrementing
xin each iteration. - Inside the loop, calculate
zeros = countZeros(x). - If
zerosis equal to the targetk, increment thecount. - Since the function
f(x)(number of zeros) is non-decreasing, ifzerosbecomes greater thank, no subsequentxwill havekzeros. So, we can break the loop. - Finally, return the
count.
Walkthrough
The number of trailing zeros in x! is determined by the number of times 5 is a factor in its prime factorization. This can be calculated using Legendre's formula: f(x) = Σ floor(x / 5^i) for i from 1 to infinity. We can implement a helper function countZeros(x) to compute this value. The main logic then iterates x from 0 upwards. In each step, it computes f(x) and compares it with k. If they are equal, a counter is incremented. The process terminates when f(x) surpasses k, as any larger x will also have more (or equal) zeros.
class Solution { public int preimageSizeFZF(int k) { int resultCount = 0; long x = 0; while (true) { long zeros = countTrailingZeros(x); if (zeros == k) { resultCount++; } else if (zeros > k) { break; } // A small optimization: if we have found at least one solution and zeros > k, // we know the answer must be 5 or 0. If resultCount > 0, it must be 5. // But for a pure brute-force, we continue until zeros > k. if (resultCount > 0 && zeros > k) { return resultCount; } x++; } return resultCount; } private long countTrailingZeros(long x) { if (x < 0) { return 0; } long count = 0; for (long i = 5; x / i >= 1; i *= 5) { count += x / i; } return count; }}Complexity
Time
O(k * log k) - The number of trailing zeros `f(x)` is approximately `x/4`. So, to reach `k` zeros, `x` needs to be around `4k`. The loop runs up to `O(k)` times. Inside the loop, `countTrailingZeros(x)` takes `O(log_5 x)` or `O(log x)` time. Thus, the total complexity is `O(k * log k)`.
Space
O(1) - We only use a few variables to store the current number, its zero count, and the result.
Trade-offs
Pros
Simple to understand and implement.
It is a direct translation of the problem statement.
Cons
The time complexity is proportional to
k, which is too slow given the constraintk <= 10^9.This approach will result in a 'Time Limit Exceeded' error on most online judges.
Solutions
Solution
class Solution {public int preimageSizeFZF(int k) { return g(k + 1) - g(k); }private int g(int k) { long left = 0, right = 5 * k; while (left < right) { long mid = (left + right) >> 1; if (f(mid) >= k) { right = mid; } else { left = mid + 1; } } return (int)left; }private int f(long x) { if (x == 0) { return 0; } return (int)(x / 5) + f(x / 5); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.