LeetCode 172. 阶乘后的零
目录
题目描述
题意分析
给定一个非负整数
n，问n!这个数写出来末尾有几个连续的零。末尾的一个零，等价于这个数含有一个因子 10；而 10 只能由 2 和 5 相乘得到。所以末尾零的个数，就是
n!的质因数分解里 2 的个数与 5 的个数取较小值。在连乘 1 到n的过程中，偶数出现的密度是 5 的倍数的两倍多，因子 2 永远富余，于是末尾零的个数完全由因子 5 的个数决定——这句话是整题的题眼，后面所有推导都建立在它上面。约束信号有两处。一是
n最大到 10000，n!是一个上万位的天文数字，任何「先把阶乘算出来再数零」的思路在 64 位整数里第一步就溢出了，题目其实是在逼你只算个数、不算数值。二是进阶要求对数时间，暗示答案是一个每步把规模缩小常数倍的循环，而不是从 1 遍历到n。边界包括
n = 0（0! = 1，答案 0）、n小于 5（一个因子 5 都没有，答案 0），以及 25、125 这类高次幂本身携带多个因子 5 的情况。
解法：统计因子 5
核心思路
一个末尾零来自一对因子
2 × 5。在1...n中，因子 2 的数量一定多于因子 5，因此答案只取决于n!中有多少个因子 5，不需要计算阶乘本身。5 的倍数至少贡献一个因子 5，共有 $\lfloor n/5 \rfloor$ 个；25 的倍数还会额外贡献一个，共有 $\lfloor n/25 \rfloor$ 个；125 的倍数再额外贡献一个。于是：
answer = n/5 + n/25 + n/125 + ...每一项都使用整数除法。实现时让
n反复除以 5，就能依次得到这些项，也避免直接计算5^k可能产生的溢出。正确性说明：若一个数含有
k个因子 5，它会在 5、25、……、$5^k$ 对应的前k层各被统计一次，恰好贡献k次；不含因子 5 的数不会进入任何一层。因此求和后不重不漏地得到n!中因子 5 的总数，也就是末尾零的个数。
解题步骤
- 初始化
answer = 0。- 每轮先令
n /= 5，得到当前层至少还能贡献一个因子 5 的数字个数。- 将当前
n加入答案，直到n变为 0。- 返回累计结果。
例如
n = 125：三层贡献依次为25、5、1，答案是31。其中 25 的倍数被多统计一层，125 又被多统计一层，正好覆盖高次幂中的额外因子 5。
代码实现
class Solution {
public int trailingZeroes(int n) {
int answer = 0;
while (n > 0) {
n /= 5;
answer += n;
}
return answer;
}
}
func trailingZeroes(n int) int {
answer := 0
for n > 0 {
n /= 5
answer += n
}
return answer
}
复杂度分析
- 时间复杂度：$O(\log_5 n)$，每轮都把
n缩小为原来的五分之一。- 空间复杂度：$O(1)$，只使用常数个变量。
关键点总结
- 不计算
n!，只统计决定末尾零数量的因子 5。- 5、25、125 等倍数要分层累计，不能只算
n / 5。- 用反复整除 5 代替显式计算 5 的幂，代码更短且没有幂次溢出风险。
易错点总结
- 只返回
n / 5：会漏掉 25、125 等数字额外携带的因子 5；n = 25时正确答案是 6，不是 5。- 先累加再除以 5：第一次会把原始
n加入答案；循环中必须先除后加。- 计算阶乘后再数零：阶乘很快溢出，且完全没有必要。
- 用
int p *= 5枚举幂次：输入范围扩大后p可能溢出；反复修改n更稳妥。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 793. 阶乘函数后 K 个零 | 困难 | 在计数函数上二分反解 |
| 233. 数字 1 的个数 | 困难 | 按位分层统计出现次数 |
| 60. 排列序列 | 困难 | 阶乘进制与逐位确定 |