0172. Factorial Trailing Zeroes¶
题目信息¶
- 题号:
阶乘后的零
- 难度:
Medium
- 主题:
数学、质因数计数、整除
- 原题:
- 重点:
把巨大阶乘的末尾结构转化为因子 5 的分层计数,并用连续整除避免幂次溢出
题目重述¶
给定非负整数 n,返回 n! 的十进制表示末尾连续零的数量。
0! = 1,所以 n = 0 时答案为 0。进阶要求在优于 O(n) 的时间内完成。
自建示例¶
输入:n = 5
输出:1
5! = 120,末尾有一个零。
输入:n = 25
输出:6
5、10、15、20 各贡献一个因子 5,25 = 5² 额外再贡献一个,共 6 个。
输入:n = 3
输出:0
3! = 6,没有因子 10。
C++ 实现¶
class Solution {
public:
int trailingZeroes(int n) {
int trailing_zeroes = 0;
int remaining = n;
while (remaining > 0) {
remaining /= 5;
trailing_zeroes += remaining;
}
return trailing_zeroes;
}
};
题解¶
计算阶乘做了哪些无用工作¶
从定义出发,可以先计算 1 * 2 * ... * n,再不断除以 10 或把结果转成字符串统计末尾
零。这条思路正确,却构造了远比答案复杂的巨大整数;固定宽度整数很快溢出,大整数的位数
和乘法成本也持续增长,而题目只问末尾的一小部分结构。
即使不保存整个阶乘,也可以逐个检查 1..n 中每个数含有多少因子 5,时间至少为
O(n)。进阶要求提示我们继续压缩:无需访问每个数,只要按“5 的倍数”成批计数。
尾零为什么只需数因子 5¶
每个十进制尾零来自一个因子 10 = 2 * 5,所以尾零数量等于阶乘质因数分解中 2 和 5
指数的较小值。
在 1..n 中,2 的倍数比 5 的倍数多,4 的倍数也不少于 25 的倍数,依此类推:
floor(n / 2^k) >= floor(n / 5^k)
把各层相加可知 n! 中因子 2 的总数不少于因子 5。每个因子 5 都能找到一个因子 2
配成 10,因此答案恰好是 n! 中因子 5 的总数。
为什么要分层计数¶
floor(n / 5) 只统计了每个 5 的倍数的第一个因子 5。像 25、50、75 这样的数还含有
第二个因子 5,125 及其倍数还含有第三个。完整计数为:
floor(n / 5)
+ floor(n / 25)
+ floor(n / 125)
+ ...
第 k 层统计 5^k 的倍数,也就是至少含有 k 个因子 5 的数。若某个数恰好
含 t 个因子 5,它会在前 t 层各出现一次,正好贡献 t,既不遗漏也不多算。
例如 n = 25 时,第一层 floor(25/5) = 5 统计 5、10、15、20、25 的首个因子;
第二层 floor(25/25) = 1 再统计 25 的第二个因子,答案为 6。只数 5 的倍数会错误地
得到 5。
连续整除压缩幂次¶
可以显式令 power 依次取 5、25、125,累加 n / power;但不断执行
power *= 5 在扩大输入范围时需要额外防止乘法溢出。代码改为维护 remaining:
remaining = floor(remaining / 5)
完成第 k 次除法后,remaining 恰为 floor(n / 5^k)。这是因为连续整数除法
满足:
floor(floor(n / 5^k) / 5) = floor(n / 5^(k+1))
所以每轮先除以 5,再把结果加入答案,正好按顺序累加公式中的一层。状态变为 0 时,当前 层和所有更高层都为 0,可以停止。
状态走读¶
对 n = 100:
轮次 remaining 除以 5 后 累计答案 本层含义
1 20 20 5 的倍数
2 4 24 25 的倍数
3 0 24 更高层无贡献
100! 因而有 24 个尾零。对 n = 0 或 n < 5,第一次或初始条件就使
remaining 为 0,没有任何因子 5,返回 0。
正确性与复杂度¶
尾零数等于因子 5 总数;分层公式恰好统计每个整数含有的每一个因子 5;循环不变量又保证
代码逐项累加该公式,直到余下项全为 0。因此返回值就是 n! 的尾零数量。
remaining 每轮缩小为原来的五分之一,循环次数为 O(log_5 n),额外空间为
O(1)。算法不计算阶乘、不创建大整数,也不显式构造 5^k。