Preimage Size of Factorial Zeroes Function
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.
- For example,
Given an integer k, return the number of non-negative integers x have the property that f(x) = k.
Examples
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 <= 10^9
Solution
Method 1 - Binary Search on Zeta Function
Intuition
The number of trailing zeroes in x! is determined by the number of times 5 divides numbers up to x. For a given k, we want to count how many x satisfy f(x) = k. It turns out that for any k, the set of x with f(x) = k is either 0 or 5 consecutive numbers. We can use binary search on the zeta function f(x) to find the leftmost and rightmost x such that f(x) = k.
Approach
Define a function f(x) that returns the number of trailing zeroes in x!. For a given k, the answer is the number of x such that f(x) = k, which we can denote as f_inv(k) = count(x | f(x) = k). This is equal to (right - left), where left is the smallest x with f(x) = k, and right is the smallest x with f(x) = k+1.
Complexity
- ⏰ Time complexity:
O(log^2(k))due to binary search and repeated division. - 🧺 Space complexity:
O(1)
Code
C++
int zeta(int x) {
int res = 0;
while (x) {
res += x / 5;
x /= 5;
}
return res;
}
int preimageSizeFZF(int k) {
auto left = [](int k) {
long l = 0, r = 5L * k + 5;
while (l < r) {
long m = l + (r - l) / 2;
int z = 0, x = m;
while (x) { z += x / 5; x /= 5; }
if (z < k) l = m + 1;
else r = m;
}
return l;
};
return (int)(left(k+1) - left(k));
}
Go
func zeta(x int) int {
res := 0
for x > 0 {
res += x / 5
x /= 5
}
return res
}
func left(k int) int {
l, r := 0, 5*k+5
for l < r {
m := l + (r-l)/2
z, x := 0, m
for x > 0 {
z += x / 5
x /= 5
}
if z < k {
l = m + 1
} else {
r = m
}
}
return l
}
func preimageSizeFZF(k int) int {
return left(k+1) - left(k)
}
Java
class Solution {
private int zeta(int x) {
int res = 0;
while (x > 0) {
res += x / 5;
x /= 5;
}
return res;
}
private long left(int k) {
long l = 0, r = 5L * k + 5;
while (l < r) {
long m = l + (r - l) / 2;
int z = 0, x = (int)m;
while (x > 0) { z += x / 5; x /= 5; }
if (z < k) l = m + 1;
else r = m;
}
return l;
}
public int preimageSizeFZF(int k) {
return (int)(left(k+1) - left(k));
}
}
Kotlin
fun zeta(x: Int): Int {
var res = 0
var x0 = x
while (x0 > 0) {
res += x0 / 5
x0 /= 5
}
return res
}
fun left(k: Int): Long {
var l = 0L
var r = 5L * k + 5
while (l < r) {
val m = l + (r - l) / 2
var z = 0
var x = m
while (x > 0) {
z += (x / 5).toInt()
x /= 5
}
if (z < k) l = m + 1
else r = m
}
return l
}
fun preimageSizeFZF(k: Int): Int = (left(k+1) - left(k)).toInt()
Python
def zeta(x: int) -> int:
res = 0
while x:
res += x // 5
x //= 5
return res
def left(k: int) -> int:
l, r = 0, 5 * k + 5
while l < r:
m = (l + r) // 2
z, x = 0, m
while x:
z += x // 5
x //= 5
if z < k:
l = m + 1
else:
r = m
return l
def preimageSizeFZF(k: int) -> int:
return left(k+1) - left(k)
Rust
fn zeta(mut x: i64) -> i64 {
let mut res = 0;
while x > 0 {
res += x / 5;
x /= 5;
}
res
}
fn left(k: i64) -> i64 {
let (mut l, mut r) = (0, 5 * k + 5);
while l < r {
let m = l + (r - l) / 2;
let mut z = 0;
let mut x = m;
while x > 0 {
z += x / 5;
x /= 5;
}
if z < k {
l = m + 1;
} else {
r = m;
}
}
l
}
fn preimage_size_fzf(k: i64) -> i64 {
left(k+1) - left(k)
}
TypeScript
function zeta(x: number): number {
let res = 0;
while (x > 0) {
res += Math.floor(x / 5);
x = Math.floor(x / 5);
}
return res;
}
function left(k: number): number {
let l = 0, r = 5 * k + 5;
while (l < r) {
let m = Math.floor((l + r) / 2);
let z = 0, x = m;
while (x > 0) {
z += Math.floor(x / 5);
x = Math.floor(x / 5);
}
if (z < k) l = m + 1;
else r = m;
}
return l;
}
export function preimageSizeFZF(k: number): number {
return left(k+1) - left(k);
}