LeetCode 面试题 16.05. 阶乘尾数
题目描述
题意分析
求非负整数
n的阶乘在十进制表示末尾有多少个连续零，题目要求对数时间。尾零个数就是乘积能连续除以多少次10，没必要先构造阶乘这个巨大整数。每个
10都需要一对质因子2和5。阶乘中的2不少于5：对任意层数k，$2^k$ 的倍数都不少于 $5^k$ 的倍数。因此每个因子5都能找到一个2配对，答案就是所有乘数中因子5的总个数。
解法：累计因子 5 的个数
核心思路
[!blue]
$1$ 到 $n$ 中，所有 $5$ 的倍数至少贡献一个因子 $5$，共有 $\lfloor n/5\rfloor$ 个。所有 $5^2$ 的倍数还各有第二个因子 $5$，再贡献 $\lfloor n/25\rfloor$；之后对 $5^3、5^4、\ldots$ 继续统计额外的一层。因此答案为：
\[\left\lfloor\frac{n}{5}\right\rfloor+\left\lfloor\frac{n}{25}\right\rfloor+\left\lfloor\frac{n}{125}\right\rfloor+\cdots\]这里重复统计同一个乘数并不是重复计数答案，而是在计算它包含的不同因子。一个乘数若恰好含
t个因子5，就会在前t层各被计一次，之后不再出现，合计正好贡献t。实现时不用保存原始
n或显式构造 $5^k$。每轮先令n /= 5，第k轮得到的商就是原始输入除以 $5^k$ 的下取整，再把它加入answer。商变成零，意味着后续更高次幂也没有倍数，循环即可结束。
解题步骤
- 初始化
answer = 0。- 当
n > 0时，把n整除 $5$，将商累加进answer。- 商变为 $0$ 后返回答案。
n == 0时，$0! = 1$ 没有尾零，循环不执行就返回零；正数小于5时，第一次整除后也直接归零。反复缩小商还避免了不断执行power *= 5时可能发生的整数溢出。
代码实现
// 依次统计 5、25、125……的倍数带来的因子 5。
class Solution {
public int trailingZeroes(int n) {
int answer = 0;
while (n > 0) {
n /= 5;
answer += n;
}
return answer;
}
}
// 依次统计 5、25、125……的倍数带来的因子 5。
func trailingZeroes(n int) int {
answer := 0
for n > 0 {
n /= 5
answer += n
}
return answer
}
复杂度分析
- 时间复杂度：$O(\log_5(n+1)+1)$，每轮把
n缩小为原来的五分之一，也覆盖零输入的常数开销。- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 尾零问题的核心不是十进制字符串，而是成对的因子 $2$ 和 $5$。
- 阶乘中偶数远多于 $5$ 的倍数，所以只需统计因子 $5$。
- 恰好含
k个因子5的乘数，在前k层各被统计一次，贡献没有遗漏或多算。- 面试追问若要求“尾零数恰为
k的n有多少个”，可以进一步对这个单调函数做二分查找。
易错点总结
[!yellow]
- 只返回
n / 5：会漏掉高次幂倍数中第二个、第三个以及更多的因子5。- 直接计算阶乘：即使使用 64 位整数，
21!也已溢出，无法覆盖题目范围。- 显式令
power *= 5：当power接近整数上界时可能溢出并导致死循环；反复整除n没有这个风险。- 把
n = 0当异常情况：$0!=1$，没有尾零，循环自然返回 $0$。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 793. 阶乘函数后 K 个零 | 困难 | 以阶乘尾零函数的单调性为基础，进一步反查达到指定尾零数的输入范围。 |
| 补充题 153. 整数的质因数分解 | 简单 | 同样分析质因子的重数，本题利用阶乘结构直接统计全部乘数中的5。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！