 内数出 n! 末尾零的个数)
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 ...递推公式并结合仓库中 递归解法源码 与 测试用例 说明该算法的实现细节与验证方式。读完后你可以掌握如何用勒让德公式Legendres formula思想计算阶乘中任意质因数的个数以及如何用 Go 递归/迭代两种方式落地该算法。题目与要求原始题目英文Given an integer n, return the number of trailing zeroes in n!.题解文档中的两个示例Example 1Input: 3Output: 0Explanation: 3! 6, no trailing zero。Example 2Input: 5Output: 1Explanation: 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可以安全地退化为只数 50 的个数 min(n! 中 2 的个数, n! 中 5 的个数) n! 中 5 的个数第三步n! 中 5 的个数 逐级除以 5 的累加。文档给出了非常直观的分组解释0~4 的阶乘里没有质因数 55~9 的阶乘里有 1 个质因数 510~14 的阶乘里有 2 个质因数 5依此类推。但要注意像 25、125 这样的数含有多个因子 525 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输入 n期望输出对应文档示例30Example 13! 6末尾无零51Example 25! 120末尾 1 个零可以补充验证更多层级以覆盖25 及以上的额外因子trailingZeroes(24) 424/5 4trailingZeroes(25) 625/5 25/25 5 1trailingZeroes(125) 3125 5 1。这些值正是公式逐层求和的直接结果。运行方式与仓库其他题目一致在仓库根目录执行go test -v ./leetcode/0172.Factorial-Trailing-Zeroes/ -run Test_Problem172仓库的 gotest.sh 则是以go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部题解做覆盖率统计本题解同样包含在内。复杂度分析与适用边界时间复杂度每层递归/循环把 n 缩小为 1/5共执行 ⌊log₅ n⌋ 1 次整数除法与加法即 O(log n)满足题目 Note 的约束空间复杂度递归写法为 O(log n) 调用栈迭代写法为 O(1)。适用前提与限制该公式针对非负整数 n 成立0! 1输出 0仓库实现依赖n/5的整数除法若 n 为负数Go 中负整除会向零取整结果不再具有数学意义使用时应保证输入非负对于 Go 的 int 类型结果远小于 n不存在溢出风险同一公式可推广到统计 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 172. Factorial Trailing Zeroes：用递归除法在 O(log n) 内数出 n! 末尾零的个数
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 ...递推公式并结合仓库中 递归解法源码 与 测试用例 说明该算法的实现细节与验证方式。读完后你可以掌握如何用勒让德公式Legendres formula思想计算阶乘中任意质因数的个数以及如何用 Go 递归/迭代两种方式落地该算法。题目与要求原始题目英文Given an integer n, return the number of trailing zeroes in n!.题解文档中的两个示例Example 1Input: 3Output: 0Explanation: 3! 6, no trailing zero。Example 2Input: 5Output: 1Explanation: 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可以安全地退化为只数 50 的个数 min(n! 中 2 的个数, n! 中 5 的个数) n! 中 5 的个数第三步n! 中 5 的个数 逐级除以 5 的累加。文档给出了非常直观的分组解释0~4 的阶乘里没有质因数 55~9 的阶乘里有 1 个质因数 510~14 的阶乘里有 2 个质因数 5依此类推。但要注意像 25、125 这样的数含有多个因子 525 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输入 n期望输出对应文档示例30Example 13! 6末尾无零51Example 25! 120末尾 1 个零可以补充验证更多层级以覆盖25 及以上的额外因子trailingZeroes(24) 424/5 4trailingZeroes(25) 625/5 25/25 5 1trailingZeroes(125) 3125 5 1。这些值正是公式逐层求和的直接结果。运行方式与仓库其他题目一致在仓库根目录执行go test -v ./leetcode/0172.Factorial-Trailing-Zeroes/ -run Test_Problem172仓库的 gotest.sh 则是以go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对全部题解做覆盖率统计本题解同样包含在内。复杂度分析与适用边界时间复杂度每层递归/循环把 n 缩小为 1/5共执行 ⌊log₅ n⌋ 1 次整数除法与加法即 O(log n)满足题目 Note 的约束空间复杂度递归写法为 O(log n) 调用栈迭代写法为 O(1)。适用前提与限制该公式针对非负整数 n 成立0! 1输出 0仓库实现依赖n/5的整数除法若 n 为负数Go 中负整除会向零取整结果不再具有数学意义使用时应保证输入非负对于 Go 的 int 类型结果远小于 n不存在溢出风险同一公式可推广到统计 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考