# 793. Preimage Size of Factorial Zeroes Function

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]`.

``````class Solution {
public:
int preimageSizeFZF(int K) {
long left = 0, right = 5L * (K + 1);
while (left < right) {
long mid = left + (right - left) / 2;
long cnt = numOfTrailingZeros(mid);
if (cnt == K) return 5;
else if (cnt < K) left = mid + 1;
else right = mid;
}
return 0;
}
long numOfTrailingZeros(long x) {
long res = 0;
for (; x > 0; x /= 5) {
res += x / 5;
}
return res;
}
};
``````

``````class Solution {
public:
int preimageSizeFZF(int K) {
long left = 0, right = 5L * (K + 1);
while (left < right) {
long mid = left + (right - left) / 2, cnt = 0;
for (long i = 5; mid / i > 0; i *= 5) {
cnt += mid / i;
}
if (cnt == K) return 5;
else if (cnt < K) left = mid + 1;
else right = mid;
}
return 0;
}
};
``````

``````x:    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
f(x): 0 0 0 0 1 1 1 1 1 2  2  2  2  2  3  3  3  3  3  4  4  4  4  4  6
g(x): 0 0 0 0 1 0 0 0 0 1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  2
``````

``````x:    5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125
g(x): 1 1  1  1  2  1  1  1  1  2  1  1  1  1  2  1  1  1  1   2   1   1   1   1   3
``````

g(x) = 0     if x % 5 != 0,
g(x) >= 1    if x % 5 == 0,
g(x) >= 2   if x % 25 == 0.

5(=15), 11(=61+5), 17(=62+5), 23(=63+5), 29(=64+5), 30(=65), 36(=31+5), 42(=31+6+5), 48(=31+6*2+5)

``````class Solution {
public:
int preimageSizeFZF(int K) {
if (K < 5) return 5;
int base = 1;
while (base * 5 + 1 <= K) {
base = base * 5 + 1;
}
if (K / base == 5) return 0;
return preimageSizeFZF(K % base);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/793

Factorial Trailing Zeroes

https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/

https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/117649/4ms-Java-Math-Solution

https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/117631/C++-O(logn)-math-solution-with-explanation

https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/117821/Four-binary-search-solutions-based-on-different-ideas

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation