Preimage Size Of Factorial Zeroes Function Problem
Description
LeetCode Problem 793.
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:
1
2
3
Input: k = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.
Example 2:
1
2
3
Input: k = 5
Output: 0
Explanation: There is no x such that x! ends in k = 5 zeroes.
Example 3:
1
2
Input: k = 3
Output: 5
Constraints:
- 0 <= k <= 10^9
Sample C++ Code using Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int Count(long long n){
long long pow = 5;
int cnt = 0;
while (true) {
int q = n / pow;
if (q == 0)
break;
cnt += q;
pow = 5 * pow;
}
return cnt;
}
int preimageSizeFZF(int k) {
if (k == 0)
return 5;
long long end = (long long) 5 * k;
long long start = 0;
long long Ans = 0;
while (start <= end) {
long long mid = start + (end - start) / 2;
long long cnt = Count(mid);
if (cnt == k) {
Ans = mid;
break;
} else if (cnt < k) {
start = mid + 1;
} else {
end = mid - 1;
}
}
if (Ans == 0)
return 0;
return 5;
}
};