LeetCode 793 - Preimage Size of Factorial Zeroes Function

This problem asks us to determine how many non-negative integers x exist such that the factorial of x ends with exactly k trailing zeroes. The function f(x) counts trailing zeroes in x!. For example, f(3) = 0 because 3! = 6 has no trailing zeroes, and f(11) = 2 because 11!

leetcodehardmathbinary-search

LeetCode Problem 793

Difficulty: 🔴 Hard
Topics: Math, Binary Search

Solution

Problem Understanding

This problem asks us to determine how many non-negative integers x exist such that the factorial of x ends with exactly k trailing zeroes. The function f(x) counts trailing zeroes in x!. For example, f(3) = 0 because 3! = 6 has no trailing zeroes, and f(11) = 2 because 11! = 39916800 has two trailing zeroes.

The input k is a non-negative integer representing the exact number of trailing zeroes we want to match. The output is also an integer, representing the number of values x for which f(x) = k. The constraints tell us that k can be as large as 10^9, which immediately rules out naive approaches that attempt to compute factorials directly or iterate through all x up to some upper bound because factorials grow extremely rapidly.

Important edge cases include small values like k = 0, which should include the factorials of 0 through 4, and values of k where no integer x can produce exactly k trailing zeroes, like k = 5. The problem guarantees k >= 0, so negative inputs do not need to be handled.

Approaches

The brute-force approach is straightforward in concept: for each non-negative integer x, compute x! and count the trailing zeroes. Count how many x satisfy f(x) = k. This approach is correct because it explicitly checks each integer for the property. However, it is infeasible because factorials grow faster than exponentially, and computing them for large x would quickly overflow memory and processing capabilities.

The optimal approach relies on the mathematical insight that trailing zeroes in factorials come from multiples of 5 (paired with even numbers). Therefore, the number of trailing zeroes in x! can be computed efficiently using:

f(x) = x//5 + x//25 + x//125 + ...

This formula counts the number of factors of 5 in x!. Given this function, the key observation is that f(x) is monotonically non-decreasing as x increases. Therefore, we can use binary search to find the smallest x with at least k trailing zeroes and the smallest x with more than k trailing zeroes. The difference of these two bounds gives the number of integers x for which f(x) = k. The result is either 0 or 5 because each block of numbers that produces the same number of trailing zeroes has exactly five consecutive integers.

Approach Time Complexity Space Complexity Notes
Brute Force O(x * log x) O(1) Compute factorial iteratively for each x until f(x) = k, infeasible for large k
Optimal O(log(k) * log(k)) O(1) Binary search over x using the trailing zero formula, efficient and scalable

Algorithm Walkthrough

  1. Define a helper function trailingZeroes(x) which computes the number of trailing zeroes in x! using the formula x//5 + x//25 + x//125 .... This runs in O(log x) time.
  2. Define a binary search function to find the smallest x such that f(x) >= k. Initialize low = 0 and high = 5 * k because f(x) increases roughly by 1 for every multiple of 5.
  3. While low < high, compute mid = (low + high) // 2. If trailingZeroes(mid) < k, set low = mid + 1. Otherwise, set high = mid. At the end, low will be the first x with f(x) >= k.
  4. Find the smallest x with f(x) = k and the smallest x with f(x) = k + 1. The difference between these two values gives the number of x with exactly k trailing zeroes. This will be either 0 (if k is impossible) or 5 (if there exists a valid x).

Why it works: The function f(x) is monotonically increasing and has a stepwise behavior where each step spans exactly five consecutive integers. By using binary search, we locate the lower bound for k and k + 1, and the difference captures all integers in that step, which guarantees correctness.

Python Solution

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        def trailingZeroes(x: int) -> int:
            count = 0
            while x > 0:
                x //= 5
                count += x
            return count
        
        def left_bound(target: int) -> int:
            low, high = 0, 5 * target
            while low < high:
                mid = (low + high) // 2
                if trailingZeroes(mid) < target:
                    low = mid + 1
                else:
                    high = mid
            return low
        
        return left_bound(k + 1) - left_bound(k)

The implementation defines trailingZeroes(x) to count factors of 5 efficiently. left_bound(target) uses binary search to find the smallest integer with at least target trailing zeroes. The difference between left_bound(k + 1) and left_bound(k) gives the number of integers with exactly k trailing zeroes, consistent with the algorithm.

Go Solution

func preimageSizeFZF(k int) int {
    trailingZeroes := func(x int) int {
        count := 0
        for x > 0 {
            x /= 5
            count += x
        }
        return count
    }

    leftBound := func(target int) int {
        low, high := 0, 5*target
        for low < high {
            mid := (low + high) / 2
            if trailingZeroes(mid) < target {
                low = mid + 1
            } else {
                high = mid
            }
        }
        return low
    }

    return leftBound(k+1) - leftBound(k)
}

The Go implementation mirrors Python closely, using closures for trailingZeroes and leftBound. Integer division handles the factor counting naturally. No special handling for empty or nil slices is needed because we only work with integers.

Worked Examples

Example 1: k = 0

left_bound(0) = 0, left_bound(1) = 5 → difference = 5

Example 2: k = 5

left_bound(5) = 25, left_bound(6) = 30 → difference = 5 → actually f(x) = 5 is impossible, check function: it returns 0 because no exact k matches a single step.

Example 3: k = 3

left_bound(3) = 15, left_bound(4) = 20 → difference = 5

State table for k = 3:

x f(x)
15 3
16 3
17 3
18 3
19 3
20 4

Number of x with f(x) = 3 is 5, consistent with algorithm.

Complexity Analysis

Measure Complexity Explanation
Time O(log k * log k) Binary search requires O(log (5k)) iterations; each iteration computes trailingZeroes in O(log x)
Space O(1) Only a few integers are stored, no additional data structures

The time complexity arises because f(x) computation takes logarithmic time relative to x, and binary search iterates logarithmically relative to k.

Test Cases

# test cases
sol = Solution()

assert sol.preimageSizeFZF(0) == 5  # 0!, 1!, 2!, 3!, 4! have 0 trailing zeroes
assert sol.preimageSizeFZF(5) == 0  # no x has exactly 5 trailing zeroes
assert sol.preimageSizeFZF(3) == 5  # 15,16,17,18,19 factorials end with 3 zeroes
assert sol.preimageSizeFZF(1) == 0  # no x has exactly 1 trailing zero
assert sol.preimageSizeFZF(1000000000) == 0  # very large k, tests upper bound
assert sol.preimageSizeFZF(24) == 5  # example with multiple of 5 trailing zeroes
Test Why
k = 0 Tests the lower boundary where multiple x produce zero trailing zeroes
k = 5 Tests case where no x exists for exact trailing zero count
k = 3 Typical case with exactly 5 x values
k = 1 Impossible case for small k
k = 10^9 Stress test for upper bound
k = 24 Another