{x}
blog image

Preimage Size of Factorial Zeroes Function

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) = 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 <= 109

Solution Explanation for Preimage Size of Factorial Zeroes Function

This problem asks to find the number of non-negative integers x such that the number of trailing zeros in x! is equal to a given integer k. The core idea is to utilize binary search to efficiently find the range of x values satisfying the condition.

Understanding the Problem:

The number of trailing zeros in x! is determined by the number of times 5 is a factor in x! (since there will always be more factors of 2 than 5). We can calculate this using the following function:

f(x) = x/5 + x/25 + x/125 + ... (summing the number of multiples of 5, 25, 125, etc., up to x).

The problem is essentially finding the number of integers x for which f(x) = k. Since f(x) is a monotonically increasing function, we can employ binary search.

Algorithm:

  1. f(x) function: This function calculates the number of trailing zeros in x!. The iterative approach is more efficient than the recursive one for large inputs.

  2. g(k) function: This is a helper function that finds the smallest integer x such that f(x) >= k. It uses binary search on the range [0, 5k] (since f(x) grows approximately linearly with x, and the upper bound of 5k is sufficient).

  3. Main Function: The main function calculates g(k+1) - g(k). This difference represents the number of integers x for which f(x) = k. This works because g(k) gives the smallest x with at least k trailing zeros, and g(k+1) gives the smallest x with at least k+1 trailing zeros. The difference between them represents the count of x values that produce exactly k trailing zeros.

Time Complexity Analysis:

  • f(x): The time complexity is O(log x) due to the iterative division.
  • g(k): The binary search on the range [0, 5k] takes O(log k) time.
  • Main Function: The main function performs two calls to g(k), so the time complexity is O(log k).

Therefore, the overall time complexity of the solution is O(log k), which is very efficient.

Space Complexity Analysis:

The space complexity is O(1) as the algorithm uses a constant amount of extra space regardless of the input size.

Code Examples (with explanations inline):

The code examples provided earlier (Python, Java, C++, Go) all implement this algorithm. The comments within the code provide further explanations. Here's a brief summary:

  • f(x): This is consistently implemented across languages as an iterative function to compute the number of trailing zeros.

  • g(k): This utilizes binary search to find the smallest x for which f(x) is greater than or equal to k.

  • Main Function: The main function efficiently computes g(k+1) - g(k) to find the required count.

This approach elegantly combines mathematical understanding with efficient algorithmic techniques to solve the problem with optimal time and space complexity.