Preimage Size of Factorial Zeroes Function — Solution
Preimage Size of Factorial Zeroes Function solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Preimage Size of Factorial Zeroes Function is a hard coding problem on math, binary search and number theory, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Math, Binary Search, Number Theory
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Let f(x) be the number of trailing zeros in x!. For instance f(3) = 0 because 3! = 6, and f(11) = 2 because 11! = 39916800.
Given k, return how many non-negative integers x satisfy f(x) == k.
Example 1
Input: k = 0
Output: 5
Explanation: f(x) = 0 for x in {0, 1, 2, 3, 4}.
Example 2
Input: k = 5
Output: 0
Explanation: f jumps from 4 (at x = 20…24) to 6 (at x = 25), skipping 5 entirely.
Example 3
Input: k = 3
Output: 5
Explanation: f(x) = 3 for x in {15, …, 19}.
Constraints
0 <= k <= 1000000000
Hints for Preimage Size of Factorial Zeroes Function
Hint 1
f(x) = x/5 + x/25 + x/125 + …— count the factors of five, since twos are always plentiful.Hint 2
fis non-decreasing and rises only at multiples of 5, always by at least one and sometimes by more.Hint 3
So the answer is only ever
5or0: binary search for the smallestxwithf(x) >= kand check whether it lands exactly onk.
How to solve Preimage Size of Factorial Zeroes Function
f is a step function that is constant on each block of five consecutive integers and jumps at every multiple of 5. So each value it attains is attained exactly five times, and values it skips are attained zero times.
Approach
- Implement
f(x)as the Legendre sumx/5 + x/25 + x/125 + …. - Binary search the smallest
x >= 0withf(x) >= k, using5(k + 1)as a safe upper bound. - Return
5iff(x) == k, otherwise0.
Why it works
Between consecutive multiples of 5 no new factor of five appears, so f is constant across each block of five. At a multiple of 5 it jumps by at least 1 — by more at multiples of 25 — which is exactly why some values of k are skipped. The upper bound works because f(5(k+1)) >= k + 1 > k.
Complexity
- Time —
O(log k · log k) - Space —
O(1)
Pitfalls
- The search space reaches about
5 × 10^9, which overflows a 32-bit integer — use 64-bit bounds. p *= 5also overflows if the loop is not stopped oncep > x.- Answering
1for a value that is attained ignores the five-wide plateau.
Reference solution
Python
def preimageSizeFZF(k: int) -> int:
def zeros(x: int) -> int:
total = 0
p = 5
while p <= x:
total += x // p
p *= 5
return total
lo, hi = 0, 5 * (k + 1)
while lo < hi:
mid = (lo + hi) // 2
if zeros(mid) >= k:
hi = mid
else:
lo = mid + 1
return 5 if zeros(lo) == k else 0Java
public static int preimageSizeFZF(int k) {
long lo = 0, hi = 5L * (k + 1);
while (lo < hi) {
long mid = (lo + hi) / 2;
if (trailingZeros(mid) >= k) hi = mid;
else lo = mid + 1;
}
return trailingZeros(lo) == k ? 5 : 0;
}
static long trailingZeros(long x) {
long total = 0, p = 5;
while (p <= x) {
total += x / p;
p *= 5;
}
return total;
}C++
static long long trailingZerosFZF(long long x) {
long long total = 0, p = 5;
while (p <= x) {
total += x / p;
p *= 5;
}
return total;
}
int preimageSizeFZF(int k) {
long long lo = 0, hi = 5LL * (k + 1);
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (trailingZerosFZF(mid) >= k) hi = mid;
else lo = mid + 1;
}
return trailingZerosFZF(lo) == k ? 5 : 0;
}JavaScript
var preimageSizeFZF = function(k) {
var zeros = function(x) {
var total = 0, p = 5;
while (p <= x) {
total += Math.floor(x / p);
p *= 5;
}
return total;
};
var lo = 0, hi = 5 * (k + 1);
while (lo < hi) {
var mid = Math.floor((lo + hi) / 2);
if (zeros(mid) >= k) hi = mid;
else lo = mid + 1;
}
return zeros(lo) === k ? 5 : 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Binary Search