Description
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) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has 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:
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def preimageSizeFZF(self, k: int) -> int:
def f(x):
if x == 0:
return 0
return x // 5 + f(x // 5)
def g(k):
return bisect_left(range(5 * k), k, key=f)
return g(k + 1) - g(k)(code-box)
class Solution {
public int preimageSizeFZF(int k) {
return g(k + 1) - g(k);
}
private int g(int k) {
long left = 0, right = 5 * k;
while (left < right) {
long mid = (left + right) >> 1;
if (f(mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return (int) left;
}
private int f(long x) {
if (x == 0) {
return 0;
}
return (int) (x / 5) + f(x / 5);
}
}(code-box)
class Solution {
public:
int preimageSizeFZF(int k) {
return g(k + 1) - g(k);
}
int g(int k) {
long long left = 0, right = 1ll * 5 * k;
while (left < right) {
long long mid = (left + right) >> 1;
if (f(mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return (int) left;
}
int f(long x) {
int res = 0;
while (x) {
x /= 5;
res += x;
}
return res;
}
};(code-box)
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)
}(code-box)
