Preimage Size of Factorial Zeroes Function solution and explanation
9 more videos on this problem
Leetcode 793 Preimage Size of Factorial Zeroes FunctionGET SDE READY · 7:52 · 1K views
793. Preimage Size of Factorial Zeroes Function (python) (Leetcode Hard)Programming Live with Larry · 20:03 · 549 views
Preimage Size of Factorial Zeroes Function - Leetcode In under 10 minutesDaily Leetcode · 8:02 · 464 views
【每日一题】793. Preimage Size of Factorial Zeroes Function, 11/05/2019Huifeng Guan · 25:01 · 357 views
Leetcode 793 | Hard | Explained | Preimage Size of Factorial Zeroes Function | ProgrammingDORAyaki Gaming 34 · 8:18 · 161 views
Leetcode 793. Preimage Size of Factorial Zeroes Function (math)LetsCode · 13:31 · 132 views
Leetcode 0793. Preimage Size of Factorial Zeroes FunctionFearless Learner · 6:20 · 129 views
793.Preimage size of factorial Zeroes function #BinaryTree#LeetCode#Java#DSA#CodingInterviewBtech wale · 6:16 · 115 views
793 preimage size of factorial zeros functionJimmy Wang · 1:53 · 80 views
No Sound Leetcode 793: Preimage Size of Factorial Zeroes FunctionExtremeProgrammer · 1:34 · 27 views
The problem
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.
Approach 1: Binary Search on Factorial Trailing Zeroes
The key to solving this problem is to realize that for any k, the values of x for which f(x) is constant form contiguous intervals. We can use binary search to find the boundaries of these intervals. The main task is to compute f(x), which gives us the number of trailing zeroes. For a given x, the trailing zeroes of x! can be found by calculating how many times 5 is a factor in numbers from 1 to x. This is given by:
f(x) = floor(x / 5) + floor(x / 25) + floor(x / 125) + ...
Use binary search to determine the first and last x such that f(x) = k.
def trailingZeroes(x):
count = 0
while x > 0:
x //= 5
count += x
return count
def preimageSizeFZF(k):
left, right = 0, 5 * (k + 1)
while left < right:
mid = (left + right) // 2
z = trailingZeroes(mid)
if z == k:
return 5
elif z < k:
left = mid + 1
else:
right = mid
return 0
k = 3
print(preimageSizeFZF(k)) # Output should be 5public class Solution {
public int trailingZeroes(int x) {
int count = 0;
while (x > 0) {
x /= 5;
count += x;
}
return count;
}
public int preimageSizeFZF(int k) {
long left = 0, right = 5L * (k + 1);
while (left < right) {
long mid = left + (right - left) / 2;
int z = trailingZeroes((int) mid);
if (z == k) return 5;
else if (z < k) left = mid + 1;
else right = mid;
}
return 0;
}
public static void main(String[] args) {
Solution sol = new Solution();
int k = 3;
System.out.println(sol.preimageSizeFZF(k)); // Output should be 5
}
}#include <iostream>
int trailingZeroes(int x) {
int count = 0;
while (x > 0) {
x /= 5;
count += x;
}
return count;
}
int preimageSizeFZF(int k) {
long long left = 0, right = 5LL * (k + 1);
while (left < right) {
long long mid = left + (right - left) / 2;
int z = trailingZeroes(mid);
if (z == k) return 5;
else if (z < k) left = mid + 1;
else right = mid;
}
return 0;
}
int main() {
int k = 3;
std::cout << preimageSizeFZF(k) << std::endl; // Output should be 5
return 0;
}function trailingZeroes(x) {
let count = 0;
while (x > 0) {
x = Math.floor(x / 5);
count += x;
}
return count;
}
function preimageSizeFZF(k) {
let left = 0, right = 5 * (k + 1);
while (left < right) {
let mid = Math.floor((left + right) / 2);
let z = trailingZeroes(mid);
if (z === k) return 5;
else if (z < k) left = mid + 1;
else right = mid;
}
return 0;
}
const k = 3;
console.log(preimageSizeFZF(k)); // Output should be 5#include <stdio.h>
int trailingZeroes(int x) {
int count = 0;
while (x > 0) {
x /= 5;
count += x;
}
return count;
}
int preimageSizeFZF(int k) {
long int left = 0, right = 5L * (k + 1);
while (left < right) {
long int mid = left + (right - left) / 2;
int z = trailingZeroes(mid);
if (z == k) return 5;
else if (z < k) left = mid + 1;
else right = mid;
}
return 0;
}
int main() {
int k = 3;
printf("%d\n", preimageSizeFZF(k)); // Output should be 5
return 0;
}using System;
public class Solution {
public int TrailingZeroes(int x) {
int count = 0;
while (x > 0) {
x /= 5;
count += x;
}
return count;
}
public int PreimageSizeFZF(int k) {
long left = 0, right = 5L * (k + 1);
while (left < right) {
long mid = left + (right - left) / 2;
int z = TrailingZeroes((int)mid);
if (z == k) return 5;
else if (z < k) left = mid + 1;
else right = mid;
}
return 0;
}
static void Main() {
Solution sol = new Solution();
int k = 3;
Console.WriteLine(sol.PreimageSizeFZF(k)); // Output should be 5
}
}In Python, the solution uses the trailingZeroes function to determine the number of trailing zeroes of factorial x. The binary search helps find the limits of x where f(x) = k. The function returns 5 or 0 based on whether there are any numbers meeting the criteria within the interval.
Time Complexity: O(log(k) * log(x)).
Space Complexity: O(1).
Approach 2: Counting Trailing Zeroes using Iterative Increment
A more direct, brute-force solution to finding the number of trailing zeroes is simply counting directly. Increment a counter and check how many numbers up to that point have exactly the desired number of trailing zeroes, using a straightforward f(x) calculation in each iteration. While less efficient than optimized approaches, this technique offers clarity and is best suited when k is small.
def f(x):
result = 0
while x > 0:
x //= 5
result += x
return result
def preimageSizeFZF(k):
count = 0
x = 0
while f(x) <= k:
if f(x) == k:
count += 1
x += 1
return count
k = 3
print(preimageSizeFZF(k)) # Output should be 5public class Solution {
public int f(int x) {
int result = 0;
while (x > 0) {
x /= 5;
result += x;
}
return result;
}
public int preimageSizeFZF(int k) {
int count = 0;
for (int x = 0; f(x) <= k; ++x) {
if (f(x) == k) count++;
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int k = 3;
System.out.println(sol.preimageSizeFZF(k)); // Output should be 5
}
}#include <iostream>
int f(int x) {
int result = 0;
while (x > 0) {
x /= 5;
result += x;
}
return result;
}
int preimageSizeFZF(int k) {
int count = 0;
for (int x = 0; f(x) <= k; ++x) {
if (f(x) == k) {
count++;
}
}
return count;
}
int main() {
int k = 3;
std::cout << preimageSizeFZF(k) << std::endl; // Output should be 5
return 0;
}function f(x) {
let result = 0;
while (x > 0) {
x = Math.floor(x / 5);
result += x;
}
return result;
}
function preimageSizeFZF(k) {
let count = 0;
let x = 0;
while (f(x) <= k) {
if (f(x) === k) count++;
x++;
}
return count;
}
const k = 3;
console.log(preimageSizeFZF(k)); // Output should be 5#include <stdio.h>
int f(int x) {
int result = 0;
while (x > 0) {
x /= 5;
result += x;
}
return result;
}
int preimageSizeFZF(int k) {
int count = 0;
for (int x = 0; f(x) <= k; ++x) {
if (f(x) == k) count++;
}
return count;
}
int main() {
int k = 3;
printf("%d\n", preimageSizeFZF(k)); // Output should be 5
return 0;
}using System;
public class Solution {
public int f(int x) {
int result = 0;
while (x > 0) {
x /= 5;
result += x;
}
return result;
}
public int PreimageSizeFZF(int k) {
int count = 0;
int x = 0;
while (f(x) <= k) {
if (f(x) == k) count++;
x++;
}
return count;
}
static void Main() {
Solution sol = new Solution();
int k = 3;
Console.WriteLine(sol.PreimageSizeFZF(k)); // Output should be 5
}
}In Python, the method iterates up to possible values, using the function f to ensure trailing zero counts are correct and increase the preimage count when k matches.
Time Complexity: O(N * log(x)).
Space Complexity: O(1).
Approach 3: Default Approach
func preimageSizeFZF(k int) int {
f := func(x int) int {
res := 0
for x != 0 {
x /= 5
res += x
}
return res
}
g := func(k int) int {
left, right := 0, k*5
for left < right {
mid := (left + right) >> 1
if f(mid) >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}
return g(k+1) - g(k)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search on Factorial Trailing Zeroes | Time Complexity: O(log(k) * log(x)). |
| Counting Trailing Zeroes using Iterative Increment | Time Complexity: O(N * log(x)). |
| Default Approach | – |
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 |
Frequently asked questions
Is Preimage Size of Factorial Zeroes Function easy or hard?
LeetCode classifies this problem as Hard because it combines number theory with binary search on a derived monotonic function. Recognizing that the trailing zero function forms blocks of size five is the key insight that simplifies the final result.
Preimage Size of Factorial Zeroes Function Python/Java solution
Most implementations define a helper function that computes trailing zeroes using repeated division by 5. Then apply binary search to find the first value where the zero count reaches k and k+1. This approach works the same way in Python, Java, C++, C#, and JavaScript.
How to solve Preimage Size of Factorial Zeroes Function in O(n)?
A straightforward method iterates through increasing values of x and computes the trailing zero count using the formula x/5 + x/25 + x/125 and so on. Count how many x values produce exactly k trailing zeroes. This approach is easy to implement but slower than binary search for large inputs.
What is the best approach for Preimage Size of Factorial Zeroes Function?
Binary search on the factorial trailing zero function is the most efficient approach. The function f(x) = number of trailing zeroes in x! is monotonic, so you can binary search for the first x where f(x) >= k and the first x where f(x) >= k+1. The difference between these two positions gives the number of valid integers, typically 5 or 0.
Is Preimage Size of Factorial Zeroes Function asked at Google/Amazon/Meta?
Problems involving factorial trailing zeroes and binary search on monotonic functions frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests mathematical reasoning, binary search application, and understanding of factorial prime factorization.
What data structure is used in Preimage Size of Factorial Zeroes Function?
No special data structure is required. The solution relies on mathematical computation of trailing zeroes and a binary search over integer ranges. The key concept is the monotonic behavior of the trailing zero function.
What is the time complexity of Preimage Size of Factorial Zeroes Function?
The optimal binary search solution runs in O(log^2 n) time and O(1) space. Each binary search step takes O(log n) iterations, and computing the trailing zero count f(x) requires O(log n) divisions by powers of 5.