Preimage Size of Factorial Zeroes Function - Video Solutions
Leetcode 793 Preimage Size of Factorial Zeroes Function
Preimage Size of Factorial Zeroes Function - Video Solution
Watch 10 video solutions for Preimage Size of Factorial Zeroes Function, a hard level problem involving Math, Binary Search. This walkthrough by GET SDE READY has 1,858 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 * 2 * 3 * ... * x and by convention, 0! = 1.
- For example,
f(3) = 0because3! = 6has no zeroes at the end, whilef(11) = 2because11! = 39916800has two zeroes at the end.
Given an integer k, return the number of non-negative integers x have the property that f(x) = k.
Example 1:
Input: k = 0 Output: 5 Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.
Example 2:
Input: k = 5 Output: 0 Explanation: There is no x such that x! ends in k = 5 zeroes.
Example 3:
Input: k = 3 Output: 5
Constraints:
0 <= k <= 109
Approach Overview
Problem Overview: Given an integer k, return how many non‑negative integers x satisfy f(x) = k, where f(x) is the number of trailing zeroes in x!. Trailing zeroes come from factors of 10 = 2 × 5, and factorials always contain more 2s than 5s, so the count depends on how many factors of 5 appear.
The trailing zero function is monotonic: as x increases, f(x) never decreases. This property allows search techniques instead of brute force enumeration.
Approach 1: Counting Trailing Zeroes using Iterative Increment (O(n log n) time, O(1) space)
Compute the factorial trailing zero count for successive values of x using the classic formula f(x) = x/5 + x/25 + x/125 .... Keep incrementing x and evaluate the zero count until it exceeds k. Track how many consecutive values produce exactly k. This works because trailing zeroes increase slowly, but scanning linearly becomes expensive when k is large. Each evaluation of f(x) costs O(log x) divisions, giving overall O(n log n) time.
Approach 2: Binary Search on Factorial Trailing Zeroes (O(log n · log n) time, O(1) space)
Use binary search on the range of possible x values. Because the trailing zero function is monotonic, you can search for the smallest x such that f(x) ≥ k. Do the same search for k + 1. The difference between the two positions gives the count of numbers whose factorial has exactly k trailing zeroes.
The helper function computes f(x) using repeated division by powers of 5, which comes directly from the mathematics of factorial prime factors. This step uses concepts from math and integer division properties. Each binary search takes O(log n) iterations and each evaluation of f(x) costs O(log n), leading to O(log² n) time overall.
An interesting property appears: the preimage size is always either 5 or 0. The binary search effectively detects whether a block of five consecutive integers maps to the same trailing zero count.
Recommended for interviews: Binary search on the trailing zero function. Interviewers expect you to recognize that f(x) is monotonic and searchable. The iterative scan demonstrates understanding of the factorial zero formula, but the binary search solution shows stronger algorithmic reasoning and scales to very large k.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Trailing Zeroes using Iterative Increment | O(n log n) | O(1) | Simple conceptual approach or when demonstrating the factorial trailing zero formula |
| Binary Search on Factorial Trailing Zeroes | O(log² n) | O(1) | Preferred for interviews and large k because the trailing zero function is monotonic |