企业官网建设流程全解析

LeetCode-Go 172. Factorial Trailing Zeroes：用递归除法在 O(log n) 内数出 n! 末尾零的个数

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇以 LeetCode-Go 仓库中 第 172 题题解文档 为主体，讲解"给定整数 n，返回 n! 末尾零的个数"这道数学题的完整解法：从质因数分解推导出只数因子 5 的核心结论，给出满足 O(log n) 时间复杂度要求的n/5 + n/25 + n/125 + ...递推公式，并结合仓库中 递归解法源码 与 测试用例 说明该算法的实现细节与验证方式。读完后你可以掌握：如何用勒让德公式（Legendre's formula）思想计算阶乘中任意质因数的个数，以及如何用 Go 递归/迭代两种方式落地该算法。

题目与要求

原始题目（英文）：

Given an integer n, return the number of trailing zeroes in n!.

题解文档中的两个示例：

• Example 1：Input: 3，Output: 0，Explanation: 3! = 6, no trailing zero。
• Example 2：Input: 5，Output: 1，Explanation: 5! = 120, one trailing zero。

题目大意（文档原文）：

给定一个整数 n，返回 n! 结果尾数中零的数量。说明: 你算法的时间复杂度应为 O(log n)。

注意最后一条 Note 是硬性约束：解法必须达到对数级时间复杂度。这意味着不能真的去算 n!（既会溢出，复杂度也远高于要求），而必须从数学上直接推导零的个数。

解题思路：末尾零的个数 = 阶乘中因子 5 的个数

文档给出的思路可以拆成三步：

第一步：零来自 2 与 5 的配对。计算 n! 有多少个后缀 0，本质是计算 n! 里有多少个因子 10，而 10 = 2 × 5，因此等价于对 n! 做质因数分解后，2 的个数与 5 的个数取较小值，即min(count2, count5)。

第二步：因子 2 永远是多余的。每两个连续整数中就至少产生一个质因数 2（偶数），而每五个整数才产生一个质因数 5。所以在任意 n! 中，因子 2 的个数严格多于因子 5 的个数，min可以安全地退化为只数 5：

0 的个数 = min(n! 中 2 的个数, n! 中 5 的个数) = n! 中 5 的个数

第三步：n! 中 5 的个数 = 逐级除以 5 的累加。文档给出了非常直观的分组解释：0~4 的阶乘里没有质因数 5，5~9 的阶乘里有 1 个质因数 5，10~14 的阶乘里有 2 个质因数 5，依此类推。但要注意，像 25、125 这样的数含有多个因子 5（25 = 5²，125 = 5³），只按"每 5 个数字一组"统计会漏掉它们。完整的统计方式是同时按 5 的幂次分组：

res = n/5 + n/(5²) + n/(5³) + ... = ((n / 5) / 5) / 5 / ...

即 n! 中因子 5 的个数，等于 n 按 5 个一组能分多少组，加上按 25 个一组能分多少组，再加上按 125 个一组能分多少组……每一轮把 n 除以 5，商直接就是"当前这一层幂次贡献的因子 5 个数"。当 n < 5 时商为 0，求和自然终止，整个算法的复杂度为 O(log₅ n)，满足题目的 O(log n) 要求。

用 n = 25 验证一下这个公式：25! 中，5、10、15、20、25 各贡献至少 1 个 5（共 5 个），25 额外再贡献 1 个 5，合计 6 个，与公式25/5 + 25/25 = 5 + 1 = 6一致。

仓库中的 Go 实现：递归版

仓库中 172. Factorial Trailing Zeroes.go 给出的解法只有 5 行有效代码：

package leetcode func trailingZeroes(n int) int { if n/5 == 0 { return 0 } return n/5 + trailingZeroes(n/5) }

从源码结构看，这段实现是对上文递推公式res = n/5 + n/25 + ...的直接翻译：

• 基准条件if n/5 == 0：当 n < 5 时，n! 中不含因子 5，直接返回 0。这里用n/5 == 0而不是n < 5做判断，与后续取整除的运算方式保持一致；
• 递归步n/5 + trailingZeroes(n/5)：当前层贡献n/5个因子 5（每 5 个数一个），然后把问题缩小为"数 (n/5)! 中因子 5 的个数"。由于 n 每递归一层缩小为原来的 1/5，递归深度为 O(log₅ n)。

该实现没有额外的空间开销（除调用栈外），也没有使用任何浮点运算，全程整数除法，避免了精度问题。

等价的迭代写法（便于理解，等价变换自同一公式）：

func trailingZeroesIter(n int) int { res := 0 for n /= 5; n > 0; n /= 5 { res += n } return res }

两者逻辑完全等价：都是不断把 n 除以 5 并累加商，区别仅在于递归用调用栈隐式保存状态，迭代用局部变量显式保存。仓库选择了更贴近数学递推定义的递归形式。

测试用例与验证

测试文件 遵循仓库统一的表驱动风格：question172结构体内嵌参数结构para172（字段s为输入 n）与答案结构ans172（字段one为期望输出），Test_Problem172遍历用例表并打印输入与trailingZeroes(p.s)的实际输出。当前覆盖的两个用例恰好对应文档中的两个 Example：

可以补充验证更多层级以覆盖"25 及以上"的额外因子：trailingZeroes(24) == 4（24/5 = 4），trailingZeroes(25) == 6（25/5 + 25/25 = 5 + 1），trailingZeroes(125) == 31（25 + 5 + 1）。这些值正是公式逐层求和的直接结果。

运行方式与仓库其他题目一致，在仓库根目录执行：

go test -v ./leetcode/0172.Factorial-Trailing-Zeroes/ -run Test_Problem172

仓库的 gotest.sh 则是以go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对全部题解做覆盖率统计，本题解同样包含在内。

复杂度分析与适用边界

• 时间复杂度：每层递归/循环把 n 缩小为 1/5，共执行 ⌊log₅ n⌋ + 1 次整数除法与加法，即 O(log n)，满足题目 Note 的约束；
• 空间复杂度：递归写法为 O(log n) 调用栈，迭代写法为 O(1)。

适用前提与限制：

1. 该公式针对非负整数 n 成立（0! = 1，输出 0）；仓库实现依赖n/5的整数除法，若 n 为负数，Go 中负整除会向零取整，结果不再具有数学意义，使用时应保证输入非负；
2. 对于 Go 的 int 类型，结果远小于 n，不存在溢出风险；
3. 同一公式可推广到"统计 n! 中任意质因子 p 的个数"：把 5 换成 p 即可（例如数因子 2 的个数用n/2 + n/4 + n/8 + ...）。本题之所以只需数 5，是因为在阶乘中 2 必然比 5 多。

小结

题解文档 的核心脉络是：末尾零 ⇔ 因子 10 ⇔ 2 与 5 配对取小 ⇔ 只数 5 ⇔n/5 + n/25 + n/125 + ...。仓库 源码 用一行递归return n/5 + trailingZeroes(n/5)落地了这一递推，测试文件 以文档中的两个示例为基准用例完成验证。掌握这个套路后，凡是"阶乘/组合数中某质因子个数"的问题，都可以用同样的"逐级除以 p 并累加"公式在 O(log n) 内直接求解。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go