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.
A major improvement over brute force is to use binary search. The function f(x) is monotonic (non-decreasing), which is a prerequisite for binary search. A key observation is that f(x) is constant for x in any interval [5m, 5m+4]. This means if there is one solution for f(x) = k, there must be exactly 5 consecutive solutions. Therefore, the problem simplifies to determining if any solution exists. We can use binary search to efficiently find if there is an x such that f(x) = k.
Algorithm
- The core idea is that the number of solutions for
f(x) = kis either 0 or 5. We can use binary search to check if at least one solution exists. - Set up a binary search for
xin a suitable range. A safe upper bound forxis5 * (k + 1)becausef(x)grows roughly asx/4. - In each step of the binary search, take the middle element
midand calculatezeros = f(mid). - If
zeros == k, we have found a value ofxfor whichf(x) = k. Based on our observation, this implies there are 5 such values. So, we can immediately return 5. - If
zeros < k, it meansmidis too small, and we need to search for a largerx. We update the search space to the right half:low = mid + 1. - If
zeros > k, it meansmidis too large, and we need to search for a smallerx. We update the search space to the left half:high = mid - 1. - If the binary search completes without finding any
xwheref(x) == k, it means no suchxexists, and the number of solutions is 0. In this case, we return 0.
Walkthrough
We are searching for an integer x within a range such that f(x) = k. Since f(x) is non-decreasing, we can apply binary search on x. The search space for x can be estimated. f(x) is approximately x/4, so x is roughly 4k. A safe upper bound like 5L * (k + 1) will suffice. The binary search algorithm will try to find an x that results in exactly k zeros. If it finds one, we know the answer is 5. If the search space is exhausted without finding such an x, it means f(x) 'jumps' over the value k (e.g., from k-1 to k+1), and no integer x produces k zeros. In that case, the answer is 0.
class Solution { public int preimageSizeFZF(int k) { long low = 0; // f(x) is approx x/4, so x is approx 4k. 5k is a safe upper bound. // For k=0, x can be up to 4. 5*(0+1)=5 is a safe bound. long high = 5L * (k + 1); while (low <= high) { long mid = low + (high - low) / 2; long zeros = countTrailingZeros(mid); if (zeros == k) { return 5; } else if (zeros < k) { low = mid + 1; } else { high = mid - 1; } } return 0; } 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((log k)^2) - The binary search performs `O(log(5k)) = O(log k)` iterations. In each iteration, `countTrailingZeros` is called, which takes `O(log_5 x) = O(log k)` time, as `x` can be up to `O(k)`.
Space
O(1) - Constant extra space is used.
Trade-offs
Pros
Very efficient with a logarithmic time complexity with respect to k.
The logic is a standard application of binary search on a monotonic function.
Cons
The time complexity, while good, can be slightly improved.
It relies on the property that the answer is either 0 or 5, which might not be immediately obvious.
This approach further refines the binary search by transforming the problem into an equivalent, but simpler one. Instead of searching for x directly, we leverage the structure of f(x). We know that if a solution exists, there must be a solution of the form x = 5m. The problem f(x) = k is thus equivalent to f(5m) = k for some integer m.
Algorithm
- The problem is transformed into finding an integer
msuch thatm + f(m) = k. - Let
g(m) = m + f(m). This function is strictly increasing, which means for anyk, there is at most onemthat satisfies the equation. - We can use binary search to find this
m. - The search space for
mis[0, k], becausem <= m + f(m) = k. - In each step of the binary search, take the middle element
mid_mand calculateval = mid_m + f(mid_m). - If
val == k, we have found the uniquem. This implies a solution exists, so we return 5. - If
val < k, we need a largerm, so we search in the right half:low = mid_m + 1. - If
val > k,mid_mis too large, so we search in the left half:high = mid_m - 1. - If the loop finishes without finding a match, no such
mexists, and we return 0.
Walkthrough
Using the property f(5m) = m + f(m), the problem of finding an x such that f(x) = k is reduced to finding an m such that m + f(m) = k. Let's define a new function g(m) = m + f(m). We can prove that g(m) is strictly increasing: g(m+1) - g(m) = (m+1 + f(m+1)) - (m + f(m)) = 1 + (f(m+1) - f(m)). Since f(m) is non-decreasing, f(m+1) - f(m) >= 0, which means g(m+1) - g(m) >= 1. The strict monotonicity of g(m) guarantees that there can be at most one integer m for which g(m) = k. We can find this m (if it exists) using binary search on the range [0, k]. If such an m is found, the answer is 5; otherwise, it's 0.
class Solution { public int preimageSizeFZF(int k) { // We are looking for m such that m + f(m) = k. // Since f(m) >= 0, m <= k. So we can search for m in [0, k]. long low = 0, high = k; while (low <= high) { long m = low + (high - low) / 2; long val = m + countTrailingZeros(m); if (val == k) { return 5; } else if (val < k) { low = m + 1; } else { high = m - 1; } } return 0; } 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((log k)^2) - The binary search for `m` is on the range `[0, k]`, taking `O(log k)` steps. Each step computes `f(m)`, which takes `O(log m) = O(log k)` time.
Space
O(1) - Constant extra space is used.
Trade-offs
Pros
Highly efficient with the same asymptotic complexity as the previous binary search approach but on a smaller search space
[0, k]vs[0, 5k].The logic is very clean due to the strictly increasing nature of the function
g(m)being searched.
Cons
Requires a mathematical transformation which might be slightly more complex to derive than a direct binary search.
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); }}class Solution {public: int preimageSizeFZF(int k) { return g(k + 1) - g(k); } int g(int k) { long long left = 0, right = 1ll * 5 * k; while (left < right) { long long mid = (left + right) >> 1; if (f(mid) >= k) { right = mid; } else { left = mid + 1; } } return (int)left; } int f(long x) { int res = 0; while (x) { x /= 5; res += x; } return res; }};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)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.