Solution Approach

The solution uses the standard binary search template to find boundaries. We need to find the first position where f(x) >= k, which maps perfectly to the "find first true" pattern.

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

def count_trailing_zeros(x):
    if x == 0:
        return 0
    return x // 5 + count_trailing_zeros(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.

2. Function findFirstWithAtLeastKZeros(k): Binary search for first x where f(x) >= k

We use the standard binary search template with first_true_index:

def find_first_with_k_zeros(k):
    left, right = 0, 5 * k
    first_true_index = -1

    while left <= right:
        mid = (left + right) // 2
        if count_trailing_zeros(mid) >= k:  # feasible condition
            first_true_index = mid
            right = mid - 1
        else:
            left = mid + 1

    return first_true_index if first_true_index != -1 else 5 * k + 1

The feasible condition is count_trailing_zeros(mid) >= k. When this is true, mid could be our answer, so we save it and search left for an even smaller value.

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

return find_first_with_k_zeros(k + 1) - find_first_with_k_zeros(k)

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

For example, if k = 1:

• find_first_with_k_zeros(1) = 5 (first number with at least 1 trailing zero)
• find_first_with_k_zeros(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: Binary search to find first x where f(x) >= 2

Using the template with left = 0, right = 10, first_true_index = -1:

Loop ends (left > right). Result: first_true_index = 10

Step 3: Binary search to find first x where f(x) >= 3

Using the template with left = 0, right = 15, first_true_index = -1:

Loop ends. Result: first_true_index = 15

Step 4: Calculate the answer Count = 15 - 10 = 5

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

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. Using the Wrong Binary Search Template

Pitfall: Using while left < right with right = mid instead of the standard template.

Why it happens: Different binary search variants exist, and developers may mix them up.

Incorrect:

while left < right:
    mid = (left + right) // 2
    if count_trailing_zeros(mid) >= k:
        right = mid
    else:
        left = mid + 1
return left

Correct (using standard template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if count_trailing_zeros(mid) >= k:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

2. Incorrect Search Space Upper Bound

Pitfall: Using an insufficient upper bound for the binary search range, such as k or 2*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 5 * k as the upper bound for right.

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: Handle k = 0 explicitly by returning 0 immediately in findFirstWithAtLeastKZeros(0).

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.

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 to count all such integers.