题目描述
f(x)
是 x!
末尾是零的数量。(回想一下 x! = 1 * 2 * 3 * ... * x
,且 0! = 1
。)
例如,f(3) = 0
,因为 3! = 6
的末尾没有零;而 f(11) = 2
,因为 11!= 39916800
末端有 2 个零。给定 K
,找出多少个非负整数 x
,有 f(x) = K
的性质。
样例
输入:K = 0
输出:5
解释:0!, 1!, 2!, 3! 和 4! 均符合 K = 0 的条件。
输入:K = 5
输出:0
解释:没有匹配到这样的 x!,符合 K = 5 的条件。
限制
K
是范围在[0, 10^9]
的整数。
算法
(数学,二分) $O(\log K)$
- 根据题意,使得
f(x) = K
的x
一定是一段区间之内的,所以我们可以先求f(x) <= K
的x
的数量s1
,然后再求f(x) <= K - 1
的数量s2
最后s1 - s2
就是答案。 - 下一步就是求
f(x) <= K
的数量。我们都知道,每个零的诞生都是2 * 5
的结果,实际上,5
的个数要远远小于2
的个数,所以我们只需要求出x
分解质因数后有多少个因数5
,就能确定f(x)
的值。 - 根据这个性质,我们可以二分最大的
t
使得,x in [0, t]
都是满足f(x) <= K
。
时间复杂度
- 两次二分的时间复杂度,二分的上限也就是 $5K$,故时间复杂度为 $O(\log K)$。
空间复杂度
- 仅用额外的常数空间,故空间复杂度为 $O(1)$。
C++ 代码
#define LL long long
class Solution {
public:
LL f(LL x) {
LL tot = 0;
while (x > 0) {
tot += x / 5;
x /= 5;
}
return tot;
}
int calc(int K) {
if (K < 0)
return 0;
LL l = 0, r = 5000000000ll;
while (l < r) {
LL mid = (l + r) >> 1;
if (f(mid) <= K) {
l = mid + 1;
} else {
r = mid;
}
}
// 这里的 l 是使得 `f(l) > K` 最小的数字。
return (int)(l);
}
int preimageSizeFZF(int K) {
return calc(K) - calc(K - 1);
}
};