172. 阶乘后的零

172. 阶乘后的零

✨核心逻辑

本题采用 数学规律（因子分解） 的策略：

1. 统计因子 5 的数量：尾随零的个数取决于阶乘中因子 10 的个数，而 10 = 2 × 5。在阶乘的连乘中，因子 2 的个数远远多于因子 5 的个数。因此，尾随零的个数 == 因子 5 的个数。
2. 逐层累加：为了找出 1 到 n 之间所有数字能贡献多少个因子 5，我们可以使用 勒让德公式：
   • 先计算 n / 5（这些数字至少贡献 1 个因子 5）。
   • 再计算 n / 25（这些数字额外再贡献 1 个因子 5）。
   • 再计算 n / 125... 以此类推。
3. 高效循环：因为 n 每次除以 5，所以不需要单独的除法公式，直接用一个 while 循环，边除以 5，边将商累加到结果中即可。

🔥代码实现（含详细变量注释）

class Solution {
    public int trailingZeroes(int n) {
        // count：记录阶乘末尾总共包含的 0 的个数
        int count = 0;
        
        // 当 n 大于 0 时，持续计算 n 中隐含的因子 5 的个数
        while (n > 0) {
            // 将当前 n 除以 5，得到一个层级下因子 5 的贡献值
            n /= 5;
            // 将本轮拿到的贡献值累加到总数中
            count += n;
        }
        
        // 返回统计出的最终结果
        return count;
    }
}

• ⏱️复杂度分析

  • 时间复杂度：：O(log_5 N)。每次循环都将 n 除以 5，因此循环次数约等于以 5 为底的 n 的对数，远远低于 O(N) 级别，符合题目进阶要求。

  • 空间复杂度：O(1)。只使用了一个额外的整型变量 count 进行累加，不需要额外的数组或递归栈空间。

🔍总结一下：

想一个问题：25/5=5 在25 的阶乘里是什么含义？？二者具有什么关系呢？

这代表着 1-25 中有 5 个数包含因子 5 ，那么和尾数 0 又是什么关系呢？10 = 2 × 5，也就是有一个 5 就有一个 10，就有一个尾数 0

因此不断让 n / 5 就能累积 5 的数量，也就是答案

期间有几个疑问：

1. 为什么不统计 2 的数量呢，因为2是有很多个的，偶数就有 2，2 无法作为统计尾数 0 的唯一标准，5则不同

2. 为什么不直接让 n/5 就能得到答案呢？因为只是说有多少个数包含因子5，这个数可能不止有一个因子5，比如 25 等等