LeetCode 172 - 阶乘后的零（Factorial Trailing Zeroes）

问题描述

给定一个整数 n，返回 n! 结果中尾随零的数量。

示例 1：

1
2
3

输入：n = 3
输出：0
解释：3! = 6，不含尾随零。

示例 2：

1
2
3

输入：n = 5
输出：1
解释：5! = 120，有一个尾随零。

示例 3：

1 2	输入：n = 0 输出：0

约束条件：

0 <= n <= 10^4

解题思路

核心洞见

阶乘末尾的零是由因子中的 2 和 5 配对产生的。在阶乘中，2 的个数总是比 5 多，因此我们只需要统计因子中 5 的个数即可。

详细分析

零的产生原理：每个尾随零都对应一个因子 10，而 10 = 2 × 5
2 和 5 的分布：在阶乘中，偶数比 5 的倍数更频繁，所以 2 的个数总是足够多
5 的来源：
- 直接包含因子 5 的数：5, 10, 15, 20, …
- 包含因子 25 的数：25, 50, 75, …（贡献两个 5）
- 包含因子 125 的数：125, 250, …（贡献三个 5）

计算方法

对于每个 5 的幂次，我们需要统计其贡献：

5¹ 的贡献：⌊n/5⌋
5² 的贡献：⌊n/25⌋
5³ 的贡献：⌊n/125⌋
…

总零的个数 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

实现细节

方法一：迭代计算

通过不断除以 5 来计算所有 5 的幂次的贡献：

func trailingZeroes(n int) int {
    ans := 0
    for n > 0 {
        n /= 5
        ans += n
    }
    return ans
}

方法二：直接计算（优化版本）

func trailingZeroes(n int) int {
    count := 0
    for n >= 5 {
        count += n / 5
        n /= 5
    }
    return count
}

代码实现

package main

/*
 * @lc app=leetcode.cn id=172 lang=golang
 *
 * [172] 阶乘后的零
 */

// @lc code=start
func trailingZeroes(n int) int {
	ans := 0
	for n > 0 {
		n /= 5
		ans += n
	}
	return ans
}
// @lc code=end

执行过程示例

以 n = 25 为例：

第一次循环：n = 25, ans = 0
- n = 25 / 5 = 5
- ans = 0 + 5 = 5
第二次循环：n = 5, ans = 5
- n = 5 / 5 = 1
- ans = 5 + 1 = 6
第三次循环：n = 1, ans = 6
- n = 1 / 5 = 0
- ans = 6 + 0 = 6
循环结束，返回 ans = 6

验证：25! = 15511210043330985984000000，末尾确实有 6 个零。

方法比较

方面	迭代计算法	直接计算法
时间复杂度	O(log n)	O(log n)
空间复杂度	O(1)	O(1)
优点	代码简洁	逻辑清晰
缺点	无	无
推荐度	★★★★★	★★★★☆

复杂度分析

时间复杂度

O(log n)

每次循环都将 n 除以 5
循环次数为 log₅(n)
由于 5 > 1，所以 log₅(n) < log₂(n) = O(log n)

空间复杂度

O(1)

只使用了常数个变量
不依赖输入规模

关键收获

重要概念

阶乘末尾零的本质：由因子 2 和 5 配对产生
数学优化：通过分析因子分布，将问题转化为统计 5 的个数
迭代技巧：通过不断除以 5 来统计所有 5 的幂次贡献

常见陷阱

直接计算阶乘：对于大数会导致溢出
忽略高次幂：只考虑单个 5 而忽略 25、125 等的贡献
边界情况：n = 0 时应该返回 0

实际应用

大数阶乘计算中的零统计
数学竞赛中的数论问题
算法复杂度分析中的对数计算

Adrian Wang's blog