Problem Description

This problem asks us to find how many non-negative integers have exactly k trailing zeros in their factorial.

First, let's understand what trailing zeros in a factorial mean. The function f(x) counts the number of zeros at the end of x! (x factorial). For example:

• 3! = 6 has 0 trailing zeros, so f(3) = 0
• 11! = 39916800 has 2 trailing zeros, so f(11) = 2

Trailing zeros in factorials come from multiplying by 10, which is the product of 2 and 5. Since there are always more factors of 2 than 5 in factorials, the number of trailing zeros equals the number of times 5 appears as a factor in the factorial.

The key insight is that the number of trailing zeros in n! can be calculated by counting how many times 5 appears as a factor in all numbers from 1 to n. This is computed as: n/5 + n/25 + n/125 + ... (using integer division).

Given an integer k, we need to find how many non-negative integers x satisfy f(x) = k. For example:

• If k = 0, the answer is 5 because f(0) = f(1) = f(2) = f(3) = f(4) = 0
• If k = 1, the answer is 5 because f(5) = f(6) = f(7) = f(8) = f(9) = 1

The solution uses binary search to find the range of values where f(x) = k. The function g(k) finds the smallest x such that f(x) >= k. The answer is then g(k+1) - g(k), which gives the count of integers with exactly k trailing zeros.

Note that for some values of k, there might be no integers x where f(x) = k, in which case the answer would be 0.

Intuition

The first observation is that trailing zeros in factorials follow a specific pattern. Since trailing zeros come from factors of 5 (paired with factors of 2), we can calculate f(x) using the formula: x/5 + x/25 + x/125 + .... This gives us a way to compute how many trailing zeros any factorial has.

Next, we notice that f(x) is a non-decreasing function - as x increases, f(x) either stays the same or increases. Moreover, f(x) increases by exactly 1 when x is divisible by 5, by 2 when divisible by 25, and so on. This means consecutive values of x often have the same f(x) value.

For example:

• f(0) = f(1) = f(2) = f(3) = f(4) = 0
• f(5) = f(6) = f(7) = f(8) = f(9) = 1
• f(10) = f(11) = f(12) = f(13) = f(14) = 2

The pattern shows that for most values of k, exactly 5 integers have f(x) = k. However, some values of k are impossible to achieve (like when k would require a number to be divisible by a higher power of 5 than possible).

Since f(x) is monotonic, we can use binary search to find boundaries. The key insight is to find:

1. The smallest x where f(x) >= k (let's call this start)
2. The smallest x where f(x) >= k+1 (let's call this end)

The difference end - start gives us the count of integers with exactly k trailing zeros.

The search space for binary search is bounded by 5*k because if an integer has k trailing zeros, it must be at least around 5*k (since we need at least k factors of 5). This gives us an efficient way to find the boundaries without checking every possible integer.

Learn more about Math and Binary Search patterns.

Solution Approach

The solution implements three key functions to solve this problem:

1. Function f(x): Calculate trailing zeros in x!

def f(x):
    if x == 0:
        return 0
    return x // 5 + f(x // 5)

This recursive function counts the number of trailing zeros in x! by counting factors of 5. It computes x//5 + x//25 + x//125 + ... through recursion. Each recursive call divides x by 5 and adds the quotient to the total count. The recursion stops when x becomes 0.

For example, f(25) returns 25//5 + 5//5 = 5 + 1 = 6.

2. Function g(k): Find the smallest x where f(x) >= k

def g(k):
    return bisect_left(range(5 * k), k, key=f)

This function uses binary search (bisect_left) to find the leftmost position where we could insert k in a sorted sequence. The search space is range(5 * k), which provides an upper bound for our search since:

• If f(x) = k, then x contains at least k factors of 5
• The smallest such x would be around 5k

The key=f parameter tells bisect_left to compare values using the function f. This effectively finds the smallest x in the range [0, 5k) where f(x) >= k.

3. Main calculation: Count integers with exactly k trailing zeros

return g(k + 1) - g(k)

The final answer uses the difference between two boundary points:

• g(k) finds the first x where f(x) >= k
• g(k+1) finds the first x where f(x) >= k+1

The difference gives us the count of integers x where f(x) = k.

For example, if k = 1:

• g(1) = 5 (first number with at least 1 trailing zero)
• g(2) = 10 (first number with at least 2 trailing zeros)
• Answer: 10 - 5 = 5 (the numbers 5, 6, 7, 8, 9 all have exactly 1 trailing zero)

The time complexity is O(log^2(k)) due to the binary search and the recursive calculation of f(x) within it.

Example Walkthrough

Let's walk through finding how many non-negative integers have exactly k = 2 trailing zeros in their factorial.

Step 1: Understanding what we're looking for We need to find all integers x where x! has exactly 2 trailing zeros. Let's check some values:

• 9! = 362,880 → 1 trailing zero
• 10! = 3,628,800 → 2 trailing zeros
• 11! = 39,916,800 → 2 trailing zeros
• 14! = 87,178,291,200 → 2 trailing zeros
• 15! = 1,307,674,368,000 → 3 trailing zeros

So we expect x = 10, 11, 12, 13, 14 to have exactly 2 trailing zeros.

Step 2: Using function f(x) to count trailing zeros Let's verify with our formula f(x) = x//5 + x//25 + x//125 + ...:

• f(10) = 10//5 + 10//25 = 2 + 0 = 2 ✓
• f(11) = 11//5 + 11//25 = 2 + 0 = 2 ✓
• f(14) = 14//5 + 14//25 = 2 + 0 = 2 ✓
• f(15) = 15//5 + 15//25 = 3 + 0 = 3 (this has 3 zeros, not 2)

Step 3: Finding boundaries with g(k) Now we use binary search to find:

• g(2): smallest x where f(x) >= 2

  • Search in range [0, 10) (since 5*k = 10)
  • Binary search checks midpoints and evaluates f(mid):
    • f(5) = 1 (too small)
    • f(7) = 1 (too small)
    • f(9) = 1 (too small)
    • f(10) = 2 (found it!)
  • Result: g(2) = 10

• g(3): smallest x where f(x) >= 3

  • Search in range [0, 15) (since 5*k = 15)
  • Binary search finds f(15) = 3
  • Result: g(3) = 15

Step 4: Calculate the answer Count = g(3) - g(2) = 15 - 10 = 5

This means exactly 5 integers (10, 11, 12, 13, 14) have factorials with exactly 2 trailing zeros.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log^2 k)

The time complexity is determined by the g function which uses bisect_left with a range of size 5k. The bisect_left performs binary search, taking O(log(5k)) = O(log k) iterations. In each iteration of the binary search, the f function is called as the key function.

The f function recursively calculates the number of trailing zeros in x! by counting factors of 5. For a number x, the recursion depth is O(log_5 x). Since x can be at most 5k in our case, the recursion depth is O(log_5(5k)) = O(log k).

Therefore, each call to g(k) has complexity O(log k) * O(log k) = O(log^2 k).

Since we call g twice (with k+1 and k), the overall time complexity remains O(log^2 k).

Space Complexity: O(log k)

The space complexity is dominated by the recursion stack in function f. When f is called with a value up to 5k, the maximum recursion depth is O(log_5(5k)) = O(log k). The bisect_left function uses O(1) additional space as it works with a virtual range and doesn't create the actual list. Therefore, the overall space complexity is O(log k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Search Space Upper Bound

Pitfall: Using an insufficient upper bound for the binary search range, such as range(k) or range(2*k), which may not cover all possible values where f(x) = k.

Why it happens: It's tempting to think that if we want k trailing zeros, we only need to search up to around k values. However, since trailing zeros come from factors of 5, and each multiple of 5 contributes at least one factor, we need approximately 5k numbers to get k trailing zeros.

Solution: Always use range(5 * k) or a slightly larger range as the search space. This ensures we cover all possible integers that could have exactly k trailing zeros.

# Wrong: Too small search space
def find_leftmost_n_with_k_zeros(target_zeros: int) -> int:
    return bisect_left(range(target_zeros), target_zeros, key=count_trailing_zeros)  # ❌

# Correct: Adequate search space
def find_leftmost_n_with_k_zeros(target_zeros: int) -> int:
    return bisect_left(range(5 * target_zeros), target_zeros, key=count_trailing_zeros)  # ✓

2. Integer Overflow in Iterative Implementation

Pitfall: When implementing the trailing zeros calculation iteratively, accumulating the result without considering potential overflow for very large values of n.

Why it happens: In languages with fixed integer sizes or when dealing with very large numbers, the iterative calculation might overflow.

Solution: Use the recursive approach shown in the solution, or ensure proper handling of large integers in your chosen language. Python handles arbitrary precision integers automatically, but in other languages you might need to use appropriate data types.

# Potentially problematic in other languages (though fine in Python)
def count_trailing_zeros_iterative(n: int) -> int:
    count = 0
    i = 5
    while i <= n:
        count += n // i
        i *= 5  # Could overflow in languages with fixed integer sizes
    return count

# Better: Recursive approach avoids accumulating large multipliers
def count_trailing_zeros_recursive(n: int) -> int:
    if n == 0:
        return 0
    return n // 5 + count_trailing_zeros_recursive(n // 5)

3. Forgetting Edge Case: k = 0

Pitfall: Not handling the special case where k = 0, which requires finding how many numbers have factorials with zero trailing zeros.

Why it happens: The formula for trailing zeros involves division by 5, and it's easy to overlook that 0!, 1!, 2!, 3!, 4! all have zero trailing zeros.

Solution: The provided solution handles this correctly through the binary search approach, but ensure your implementation doesn't have special conditions that break for k = 0.

# The solution naturally handles k=0:
# g(0) = 0 (first number with at least 0 trailing zeros)
# g(1) = 5 (first number with at least 1 trailing zero)
# Result: 5 - 0 = 5 (correct: 0!, 1!, 2!, 3!, 4! all have 0 trailing zeros)

4. Misunderstanding the Problem: Looking for Exact Match vs Range

Pitfall: Trying to find a single value x where f(x) = k instead of counting all values in the range.

Why it happens: The problem asks for the count of integers, not just whether such an integer exists. It's easy to misread and implement a solution that only checks existence.

Solution: Remember that the answer is a count. The pattern is that consecutive integers often have the same number of trailing zeros in their factorials (e.g., 5!, 6!, 7!, 8!, 9! all have exactly 1 trailing zero). The solution correctly uses the difference g(k+1) - g(k) to count all such integers.