LeetCode 793. 阶乘函数后 K 个零
题目描述
题意分析
给定
k，统计有多少个非负整数x使x!末尾恰好有k个零。需要返回符合条件的x的数量，不能只返回其中一个；0! = 1，所以零也必须纳入候选范围。
解法：因子五计数 + 双边界二分
核心思路
[!blue]
一个尾零来自一对因子二和五，阶乘中的因子二比五充足，因此只需统计因子五。每个五的倍数贡献至少一个五，二十五的倍数额外贡献一个，一百二十五的倍数再额外贡献一个，得到
f(x) = floor(x/5) + floor(x/25) + ...。反复把x除以五并累加商，就能算出这个值，既不计算阶乘，也不必显式维护五的幂。
f(x)随x单调不减，所以所有满足f(x) = k的整数只能构成一个连续区间，也可能根本不存在。令left为第一个满足f(x) >= k的位置，right为第一个满足f(x) > k的位置，则目标区间是[left, right)，答案为right - left。函数若跳过k，两个边界相同，差值自然为零。两个边界都用寻找首个满足条件的位置的二分。中点满足当前条件，就令
hi = mid保留它并向左找；不满足则令lo = mid + 1，排除中点及所有更小位置。lo < hi时两种操作都会缩小区间，最终重合处就是所求边界。搜索从零开始，代码取上界
5 * (k + 1) + 5。在这个位置，仅第一项floor(x/5)就已等于k + 2，所以两个二分的右端都满足条件，不会遗漏答案。k可达十亿，上界、累计零数和中点都使用 64 位整数。结果实际上只能为零或五：对固定
q，5q到5q+4的因子五总数相同；到了下一个五的倍数，至少再增加一个因子五。因此一个能取到的函数值恰好对应五个连续整数，而较大的跳跃会使某些k完全没有原像。代码用边界差统一处理两种结果。
解题步骤
- 实现反复除以五并累加商的尾零计数函数。
- 在从零到上述宽整数上界的区间内，二分第一个
f(x) >= k的位置。- 在相同范围内，二分第一个
f(x) > k的位置。- 返回第二个位置减去第一个位置；
k = 0也由同一边界规则处理。
代码实现
class Solution {
public int preimageSizeFZF(int k) {
long left = lowerBound(k);
long right = upperBound(k);
return (int) (right - left);
}
private long lowerBound(int k) {
long lo = 0;
long hi = 5L * (k + 1) + 5;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
// 左边界寻找第一个零数不少于目标的位置。
if (countZero(mid) >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
private long upperBound(int k) {
long lo = 0;
long hi = 5L * (k + 1) + 5;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
// 右边界寻找第一个严格超过目标的位置，两边界相减即个数。
if (countZero(mid) > k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
private long countZero(long x) {
long count = 0;
while (x > 0) {
// 逐次除以五，累加五、二十五等幂次提供的因子数。
x /= 5;
count += x;
}
return count;
}
}
func preimageSizeFZF(k int) int {
left := lowerBound(k)
right := upperBound(k)
return int(right - left)
}
func lowerBound(k int) int64 {
var lo int64 = 0
var hi int64 = 5*int64(k+1) + 5
for lo < hi {
mid := lo + (hi-lo)/2
// 左边界寻找第一个零数不少于目标的位置。
if countZero(mid) >= int64(k) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
func upperBound(k int) int64 {
var lo int64 = 0
var hi int64 = 5*int64(k+1) + 5
for lo < hi {
mid := lo + (hi-lo)/2
// 右边界寻找第一个严格超过目标的位置，两边界相减即个数。
if countZero(mid) > int64(k) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
func countZero(x int64) int64 {
var count int64 = 0
for x > 0 {
// 逐次除以五，累加五、二十五等幂次提供的因子数。
x /= 5
count += x
}
return count
}
复杂度分析
- 时间复杂度：$O(\log^2(k+2))$。二分区间规模为 $O(k+1)$，每次计数又需要对中点反复除以五。
- 空间复杂度：$O(1)$，只使用区间边界、中点和累计计数。
关键点总结
[!green]
- 尾零数是因子五的总数，必须包含高次五的倍数的额外贡献。
- 用“至少为
k”与“严格大于k”的两个边界界定全部解。- 五个整数一组形成相同尾零数，跳过的目标值由边界相等自动识别。
易错点总结
[!yellow]
- 两次二分使用相同条件，会得到两个相同边界，错误地总返回零。
- 只计算
x / 5，会遗漏二十五、一百二十五等提供的额外因子。- 下界从一开始会漏掉
x = 0，影响零尾零的计数。- 上界乘法必须在宽整数类型中进行，不能先用窄整数溢出后再赋值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 172. 阶乘后的零 | 中等 | 以阶乘尾零计数为单调函数，查第一个达到k及k+1的位置，边界差就是原像大小。 |
| 278. 第一个错误的版本 | 简单 | 复用寻找第一个满足单调条件的位置，本题需要两次边界查询来计算区间长度。 |