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.
f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has 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 <= 109The key observation is understanding how trailing zeroes are formed in factorial numbers. The number of trailing zeroes in n! depends on how many times the factor 5 appears in the prime factorization of numbers from 1 to n. This can be computed using the formula f(n) = n/5 + n/25 + n/125 .... The challenge is determining how many integers x satisfy f(x) = k.
Instead of checking each value, we leverage the fact that the function f(n) is monotonic. This allows the use of binary search to find whether a value producing exactly k trailing zeroes exists. Interestingly, the structure of the function means the preimage size is either 0 or 5. By performing a binary search over a safe upper bound and evaluating f(mid), we can determine whether such a block of values exists.
This approach efficiently narrows the search space while computing trailing zeroes in logarithmic steps. The overall method keeps computations lightweight and avoids brute-force enumeration.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Trailing Zero Count | O(log n * log n) | O(1) |
| Trailing Zero Calculation f(n) | O(log n) | O(1) |
NeetCodeIO
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of factorial trailing zero problems appear in technical interviews at major tech companies. This problem tests mathematical insight, understanding of monotonic functions, and the ability to apply binary search to non-array problems.
Binary search works because the trailing zero function f(n) increases monotonically as n grows. This allows us to quickly locate whether any number produces exactly k trailing zeroes without checking every integer.
Trailing zeroes in factorials come from factors of 10, which are produced by pairs of 2 and 5. Since factors of 2 are abundant, the count depends on the number of factors of 5 in numbers up to n. This is computed using repeated division by powers of 5.
The optimal approach uses binary search combined with a mathematical formula for counting trailing zeroes in factorials. By evaluating f(n) = n/5 + n/25 + n/125..., we can check if a value produces exactly k zeroes. Due to the monotonic nature of the function, binary search efficiently determines whether a valid range exists.