172. 阶乘后的零
题目描述
输入整数 n，求 n! 的末尾有几个连续的 0，返回这个个数。
其中 n! = n * (n - 1) * ... * 2 * 1，并约定 0! = 1。
示例 1
输入：n = 3 输出：0
解释：3! = 6，末尾没有 0。
示例 2
输入：n = 5 输出：1
解释：5! = 120，末尾有 1 个 0。
示例 3
输入：n = 0 输出：0
解释：0! = 1，末尾没有 0。
数据范围
0 <= n <= 10^4
进阶：能否设计时间复杂度为对数级的算法？
解题思路：统计因子 5（反复除 5）
末尾的每个 0 来自一个因子 10 = 2 × 5。因子 2 远比 5 多，所以只需数 1..n 中一共有多少个因子 5：5 的倍数各贡献一个（n//5 个），25 的倍数再多贡献一个（n//25 个），125 的倍数再多一个……不断把 n 除以 5 并累加即可。
为什么正确
第 t 轮后 n 等于 原 n // 5^t，即 1..原 n 中 5^t 的倍数个数；ans 是前 t 层贡献之和。
复杂度分析
时间 O(log₅ n)，空间 O(1)。
易错点
只算 n // 5 会漏掉 25、125 等数里多出来的因子 5。不要真的计算 n!，它很快就会溢出。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def trailingZeroes(self, n: int) -> int:
ans = 0
while n:
n //= 5
ans += n
return ansclass Solution {
public int trailingZeroes(int n) {
int ans = 0;
while (n != 0) {
n /= 5;
ans += n;
}
return ans;
}
}class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while (n) {
n /= 5;
ans += n;
}
return ans;
}
};func trailingZeroes(n int) int {
ans := 0
for n != 0 {
n /= 5
ans += n
}
return ans
}var trailingZeroes = function(n) {
let ans = 0;
while (n) {
n = Math.floor(n / 5);
ans += n;
}
return ans;
};function trailingZeroes(n: number): number {
let ans = 0;
while (n) {
n = Math.floor(n / 5);
ans += n;
}
return ans;
}其他解法
逐个统计是按数累加因子 5；主解法按“5 的倍数、25 的倍数…”分层计数，把时间降到 O(log n)。
解法 2：逐个数统计因子 5 时间 O(n)，空间 O(1)
末尾 0 的个数等于 n! 中质因子 5 的个数，因为因子 2 更多。枚举 5、10、15 … 不超过 n 的每个 5 的倍数，反复除以 5，累加它含有的因子 5 的个数。
直接对应“数因子 5”的定义，容易理解。内层平均只执行常数次，整体约 O(n)，比主解法慢。
class Solution:
def trailingZeroes(self, n: int) -> int:
ans = 0
for i in range(5, n + 1, 5):
x = i
while x % 5 == 0:
ans += 1
x //= 5
return ansclass Solution {
public int trailingZeroes(int n) {
int ans = 0;
for (int i = 5; i <= n; i += 5) {
for (int x = i; x % 5 == 0; x /= 5) ans++;
}
return ans;
}
}class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
for (int i = 5; i <= n; i += 5) {
for (int x = i; x % 5 == 0; x /= 5) ans++;
}
return ans;
}
};func trailingZeroes(n int) int {
ans := 0
for i := 5; i <= n; i += 5 {
for x := i; x%5 == 0; x /= 5 {
ans++
}
}
return ans
}var trailingZeroes = function(n) {
let ans = 0;
for (let i = 5; i <= n; i += 5) {
for (let x = i; x % 5 === 0; x /= 5) ans++;
}
return ans;
};function trailingZeroes(n: number): number {
let ans = 0;
for (let i = 5; i <= n; i += 5) {
for (let x = i; x % 5 === 0; x /= 5) ans++;
}
return ans;
};