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 <= 109Problem Overview: Given an integer k, return how many non‑negative integers x satisfy f(x) = k, where f(x) is the number of trailing zeroes in x!. Trailing zeroes come from factors of 10 = 2 × 5, and factorials always contain more 2s than 5s, so the count depends on how many factors of 5 appear.
The trailing zero function is monotonic: as x increases, f(x) never decreases. This property allows search techniques instead of brute force enumeration.
Approach 1: Counting Trailing Zeroes using Iterative Increment (O(n log n) time, O(1) space)
Compute the factorial trailing zero count for successive values of x using the classic formula f(x) = x/5 + x/25 + x/125 .... Keep incrementing x and evaluate the zero count until it exceeds k. Track how many consecutive values produce exactly k. This works because trailing zeroes increase slowly, but scanning linearly becomes expensive when k is large. Each evaluation of f(x) costs O(log x) divisions, giving overall O(n log n) time.
Approach 2: Binary Search on Factorial Trailing Zeroes (O(log n · log n) time, O(1) space)
Use binary search on the range of possible x values. Because the trailing zero function is monotonic, you can search for the smallest x such that f(x) ≥ k. Do the same search for k + 1. The difference between the two positions gives the count of numbers whose factorial has exactly k trailing zeroes.
The helper function computes f(x) using repeated division by powers of 5, which comes directly from the mathematics of factorial prime factors. This step uses concepts from math and integer division properties. Each binary search takes O(log n) iterations and each evaluation of f(x) costs O(log n), leading to O(log² n) time overall.
An interesting property appears: the preimage size is always either 5 or 0. The binary search effectively detects whether a block of five consecutive integers maps to the same trailing zero count.
Recommended for interviews: Binary search on the trailing zero function. Interviewers expect you to recognize that f(x) is monotonic and searchable. The iterative scan demonstrates understanding of the factorial zero formula, but the binary search solution shows stronger algorithmic reasoning and scales to very large k.
The key to solving this problem is to realize that for any k, the values of x for which f(x) is constant form contiguous intervals. We can use binary search to find the boundaries of these intervals. The main task is to compute f(x), which gives us the number of trailing zeroes. For a given x, the trailing zeroes of x! can be found by calculating how many times 5 is a factor in numbers from 1 to x. This is given by:
f(x) = floor(x / 5) + floor(x / 25) + floor(x / 125) + ...
Use binary search to determine the first and last x such that f(x) = k.
This C solution first defines a helper function trailingZeroes to calculate the number of trailing zeroes in x!. The main function preimageSizeFZF uses binary search between 0 and 5*(k + 1) to find if any number produces exactly k trailing zeroes. If found, the range size is 5, reflecting the preimage size; otherwise, it's 0.
Time Complexity: O(log(k) * log(x)) where x is the maximum number such that f(x) = k.
Space Complexity: O(1).
A more direct, brute-force solution to finding the number of trailing zeroes is simply counting directly. Increment a counter and check how many numbers up to that point have exactly the desired number of trailing zeroes, using a straightforward f(x) calculation in each iteration. While less efficient than optimized approaches, this technique offers clarity and is best suited when k is small.
In this C approach, the function f is utilized in a brute force manner. It increments through integers, counting each one that matches the trailing zero requirement by calling itself and adjusting the count accordingly.
Time Complexity: O(N * log(x)), where N is the feasible range to be checked.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Binary Search on Factorial Trailing Zeroes | Time Complexity: O(log(k) * log(x)) where x is the maximum number such that f(x) = k. |
| Counting Trailing Zeroes using Iterative Increment | Time Complexity: O(N * log(x)), where N is the feasible range to be checked. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Trailing Zeroes using Iterative Increment | O(n log n) | O(1) | Simple conceptual approach or when demonstrating the factorial trailing zero formula |
| Binary Search on Factorial Trailing Zeroes | O(log² n) | O(1) | Preferred for interviews and large k because the trailing zero function is monotonic |
Leetcode 793 Preimage Size of Factorial Zeroes Function • GET SDE READY • 1,794 views views
Watch 9 more video solutions →Practice Preimage Size of Factorial Zeroes Function with our built-in code editor and test cases.
Practice on FleetCode