#793

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Preimage Size of Factorial Zeroes Function

Solve for the number of integers whose factorial ends with a specific number of zeroes using binary search techniques.

Problem Statement

Given an integer k, the problem requires you to determine how many non-negative integers x have the property that the factorial of x, denoted x!, ends with exactly k trailing zeroes. The number of trailing zeroes in a factorial is determined by how many times 10 can be factored from the number, which is equivalent to counting the number of pairs of 2 and 5 factors in x!. Since factors of 2 are more abundant, the number of trailing zeroes depends primarily on the number of factors of 5.

For example, 0! and 1! both result in zero trailing zeroes, while larger factorials will start to accumulate trailing zeroes as factors of 5 appear. The task asks you to find the count of integers x such that the number of trailing zeroes in x! is equal to a given value k. For larger k values, there may be no solution, while for smaller values, the answer is constrained to a finite range of values.

Examples

Example 1

Input: k = 0

Output: 5

0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

Example 2

Input: k = 5

Output: 0

There is no x such that x! ends in k = 5 zeroes.

Example 3

Input: k = 3

Output: 5

Example details omitted.

Constraints

0 <= k <= 109

Solution Approach

Binary Search for Range

The key to solving this problem efficiently is using binary search over the possible values of x. Since the number of trailing zeroes in x! increases as x increases, we can use binary search to find the first and last values of x that result in exactly k trailing zeroes. This approach optimizes the search space and allows us to avoid a brute force solution.

Counting Trailing Zeroes in Factorial

To implement binary search effectively, we need to compute the number of trailing zeroes in x! efficiently. This can be done by counting how many times x is divisible by powers of 5 (i.e., 5, 25, 125, etc.). The sum of these counts gives the total number of trailing zeroes in x!. This step is crucial for comparing against the given k.

Edge Case Handling

It is important to handle edge cases where there may be no solution. For example, if k is too large, there may be no values of x that satisfy the condition. Similarly, the binary search must also account for scenarios where the exact number of trailing zeroes is never achieved, and the result should be zero in such cases.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the binary search approach is O(log(n)), where n is the upper bound of possible factorial values, typically set to 5 * 10^8 for practical computation limits. The space complexity is O(1) since we only need a few variables to track the binary search bounds and trailing zeroes count.

What Interviewers Usually Probe

Tests the candidate's understanding of binary search in a mathematical context.
Assesses problem-solving efficiency through an optimization approach.
Evaluates ability to implement mathematical algorithms for large input sizes.

Common Pitfalls or Variants

Common pitfalls

Overlooking the fact that trailing zeroes only depend on the factors of 5.
Failing to account for the fact that there might be no valid x for large k values.
Using brute force or non-optimal solutions instead of binary search to minimize time complexity.

Follow-up variants

What happens if the problem were to ask for x! to end with exactly k+1 trailing zeroes instead of k?
How would the solution change if factorials had to end with an even number of trailing zeroes?
If k is a very large number, how would we adjust the approach to ensure correctness and efficiency?

FAQ

What is the time complexity of the solution?

The time complexity is O(log(n)), where n is the upper bound of possible factorial values.

How do we calculate the number of trailing zeroes in x!?

We count how many times x is divisible by powers of 5 (e.g., 5, 25, 125), and sum these counts.

What if there is no integer x such that x! ends with exactly k trailing zeroes?

In such cases, the solution should return 0 as no valid x exists.

How does binary search improve the time complexity here?

Binary search reduces the search space logarithmically, allowing for an efficient solution instead of checking every possible x.

Why are trailing zeroes in factorials determined by factors of 5?

Trailing zeroes in a factorial are formed by pairs of 2 and 5 factors. Since there are more factors of 2 than 5, the number of trailing zeroes is determined by the number of 5s.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

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)

Continue Practicing

#754 reach a number #710 random pick with blacklist #878 nth magical number