LeetCode 面试题 16.05. 阶乘尾数

2026-03-28 HGNULB 约 3 分钟

文章信息 3 个分类 1 个标签

分类

题目描述

✅ 面试题 16.05. 阶乘尾数

题意分析

题目目标：给定非负整数 n，求 $n!$ 的十进制表示末尾有多少个连续的零。
关键转化：一个尾零来自一个因子 $10=2\times5$。阶乘中因子 $2$ 的数量一定多于因子 $5$，所以答案只取决于所有乘数一共贡献了多少个因子 $5$。
重复贡献：$25$ 会贡献两个 $5$，$125$ 会贡献三个，因此不能只统计 $5$ 的倍数。
朴素瓶颈：先计算 $n!$ 再数末尾零会很快溢出，而且计算了大量无关数位；直接计数质因子即可。

解法：累计因子 5 的个数

核心思路

$1$ 到 $n$ 中有 $\lfloor n/5\rfloor$ 个数至少贡献一个因子 $5$；其中又有 $\lfloor n/25\rfloor$ 个数额外贡献一个；之后继续统计 $125,625,\ldots$。
因而答案为：
\[\left\lfloor\frac{n}{5}\right\rfloor+\left\lfloor\frac{n}{25}\right\rfloor+\left\lfloor\frac{n}{125}\right\rfloor+\cdots\]
每轮直接令 n /= 5，当前商就是这一层应新增的贡献，既简洁也避免显式计算不断增长的 $5^k$。

解题步骤

初始化 answer = 0。

当 n > 0 时，把 n 整除 $5$，将商累加进 answer。

商变为 $0$ 后返回答案。

以 n = 100 为例：第一轮得到 $100/5=20$，第二轮得到 $20/5=4$，第三轮为 $0$，所以尾零数是 $20+4=24$。其中多出的 $4$ 正是 $25,50,75,100$ 各自额外贡献的一个因子 $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)$，每轮把 n 缩小为原来的五分之一。

空间复杂度：$O(1)$。

关键点总结

尾零问题的核心不是十进制字符串，而是成对的因子 $2$ 和 $5$。

阶乘中偶数远多于 $5$ 的倍数，所以只需统计因子 $5$。

$5^k$ 的倍数会在第 $1$ 到第 $k$ 层各被统计一次，恰好对应其包含的 $k$ 个因子 $5$。

面试追问若要求“尾零数恰为 k 的 n 有多少个”，可以进一步对这个单调函数做二分查找。

易错点总结

只返回 n / 5：n = 25 时会得到 $5$，但正确答案是 $5+1=6$，因为 $25$ 还多含一个因子 $5$。

直接计算阶乘：即使使用 64 位整数，21! 也已溢出，无法覆盖题目范围。

显式令 power *= 5：当 power 接近整数上界时可能溢出并导致死循环；反复整除 n 没有这个风险。

把 n = 0 当异常情况：$0!=1$，没有尾零，循环自然返回 $0$。

相似题目

题目	难度	考察点
172. 阶乘后的零	中等	质因子计数
793. 阶乘函数后 K 个零	困难	单调性与二分