LeetCode 172. 阶乘后的零
题目描述
题意分析
求 $n!$ 末尾连续零的数量，而不是其中所有零的数量。每个尾零对应一个因子 $10=2\times5$，因此答案取决于阶乘中因子 2 与因子 5 能配成多少对，无需计算阶乘本身。
解法：统计因子 5
核心思路
[!blue]
在 $1$ 到 $n$ 中，$2^k$ 的倍数数量总不少于 $5^k$ 的倍数数量，所以阶乘中的因子 2 一定足够与所有因子 5 配对。问题便转成统计因子 5 的总个数。
每个 5 的倍数至少提供一个因子 5，先计入 $\lfloor n/5\rfloor$；每个 25 的倍数至少还有一个，再计入 $\lfloor n/25\rfloor$；更高次幂同理。一个恰好含 $k$ 个因子 5 的乘数会在前 $k$ 层各被统计一次，正好贡献 $k$，既不遗漏也不多算。因此答案为 $\lfloor n/5\rfloor+\lfloor n/25\rfloor+\lfloor n/125\rfloor+\cdots$。
不必逐次计算 5 的幂。设原输入为 $N$，反复执行
n /= 5后，第 $k$ 轮的n就是 $\lfloor N/5^k\rfloor$，将它加入answer即可。除到 0 时，更高层也全部为 0，可以结束；这正好满足题目对数时间的进阶要求。
解题步骤
- 初始化
answer = 0。- 每轮先令
n /= 5，得到当前层至少还能贡献一个因子 5 的数字个数。- 将当前
n加入答案，直到n变为 0。- 返回累计结果。
当 $n=0$ 时，$0!=1$ 没有尾零，循环不执行便返回 0；当 $n<5$ 时，第一次整除就得到 0，也会自然返回正确结果。
代码实现
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(n+1))$，每轮都把
n缩小为原来的五分之一。- 空间复杂度：$O(1)$，只使用常数个变量。
关键点总结
[!green]
- 不计算
n!，只统计决定末尾零数量的因子 5。- 5、25、125 等倍数要分层累计，不能只算
n / 5。- 用反复整除 5 代替显式计算 5 的幂，直接得到每一层的数量，也避免构造大数。
易错点总结
[!yellow]
- 只返回
n / 5：只统计每个 5 的倍数贡献的第一个因子，会漏掉高次幂额外携带的因子 5。- 先累加再除以 5：第一次会把原始
n加入答案；循环中必须先除后加。- 计算阶乘后再数零：阶乘很快溢出，且完全没有必要。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 793. 阶乘函数后 K 个零 | 困难 | 本题计算给定n的尾零数，原题利用该函数单调性反查产生k个尾零的输入范围。 |
| 补充题 153. 整数的质因数分解 | 简单 | 同样关注质因子重数，本题无需逐个分解乘数，可直接统计5的各次幂倍数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！