Preimage Size of Factorial Zeroes Function

Problem Description

Given an integer k, return the number of non-negative integers x that have the property that f(x) = k, where f(x) is the number of trailing zeroes in x!.

Key Insights

• The trailing zeroes in a factorial are produced by the factors of 10, which are made up of pairs of 2 and 5.
• Since there are typically more factors of 2 than 5, the number of trailing zeroes is determined by the number of times 5 is a factor in the numbers from 1 to x.
• The function f(x) can be computed as:
  • f(x) = floor(x/5) + floor(x/25) + floor(x/125) + ...
• The function f(x) is non-decreasing.
• To find the number of integers x such that f(x) = k, we can find the range of x values that satisfy this condition.

Space and Time Complexity

Time Complexity: O(log x) for finding f(x) and O(log k) for binary search, leading to an overall complexity of O(log k). Space Complexity: O(1) since we only use a few variables.

Solution

To solve this problem, we can use a binary search approach to find the bounds of x values that yield the same number of trailing zeroes (f(x) = k). The key steps are:

1. Implement a function to calculate f(x).
2. Use binary search to find the smallest integer x where f(x) = k.
3. Use binary search to find the smallest integer x where f(x) = k + 1.
4. The difference between these two results gives the count of integers x such that f(x) = k.

Code Solutions