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 2 zeroes at the end. Given K, find how many 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. Note:
K will be an integer in the range [0, 10^9].
Solution:
class Solution {
static int f(int64_t n) {
int k = 0;
while (n) {
n /= 5;
k += n;
}
return k;
}
static int64_t findLowerBound(int k) {
// k = f(n) = n/5 + n/25 + n/125 .. <= n/4
// -> n >= 4k
int64_t n_lb = 4 * (int64_t)k;
// k = f(n) = n/5 + n/25 + n/125 .. >= (n - 5)/5
// -> n <= 5(k + 1)
int64_t n_ub = 5 * ((int64_t)k + 1);
if (f(n_lb) == k) return n_lb;
while (n_lb + 1 < n_ub) {
int64_t n_mid = (n_lb + n_ub) / 2;
if (f(n_mid) < k) n_lb = n_mid;
else n_ub = n_mid;
}
return n_ub;
}
public:
int preimageSizeFZF(int K) {
return K == 0 ? 5 : (findLowerBound(K + 1) - findLowerBound(K));
}
};