LeetCode 172题解析：阶乘尾随零的数学优化解法

四达印务

1. 问题背景与核心思路拆解

第一次看到LeetCode 172题「阶乘后的零」时，很多人会和我一样产生错觉——这不就是统计阶乘结果末尾有多少个零吗？直接计算阶乘然后数零不就行了？但真正动手实现时才发现，当n稍微大一点（比如n=20），20!的结果就已经是个天文数字了，用常规方法根本无法存储和计算。

1.1 尾随零的本质

经过仔细分析题目，我发现问题的关键在于理解「尾随零」产生的本质原因。每个尾随零实际上都对应着一个因子10，而10=2×5。在阶乘的计算过程中：

2的因子数量非常丰富（每两个数就有一个偶数）
5的因子相对稀缺（每五个数才出现一次）

因此，尾随零的数量实际上由阶乘中5的因子数量决定。这个洞察是解决整个问题的关键转折点。

1.2 数学原理验证

为了验证这个结论，我手动计算了几个例子：

5! = 120 → 1个零（5=5×1）
10! = 3628800 → 2个零（10=5×2，但25=5×5会额外贡献）
25! → 6个零（25/5=5，25/25=1，5+1=6）

这些例子都验证了我们的结论：尾随零的数量等于n!中5的因子总数。

2. 暴力解法实现与优化空间

2.1 暴力解法实现细节

最初的暴力解法思路很直接：遍历1到n的所有整数，统计每个数中包含的5的因子数量，然后累加。用TypeScript实现的代码如下：

typescript复制function trailingZeroes(n: number): number {
    let count = 0;
    for (let i = 5; i <= n; i += 5) {
        let current = i;
        while (current % 5 === 0) {
            count++;
            current /= 5;
        }
    }
    return count;
};

代码优化点：

直接从5开始遍历，步长为5（因为只有5的倍数才包含5的因子）
使用while循环分解每个数中的5因子

2.2 复杂度分析与局限性

虽然这个解法正确，但它的时间复杂度是O(n log n)：

外层循环执行n/5次
内层while循环在最坏情况下执行log₅n次

当n=10^9时，这个算法明显会超时。在我的测试中，当n>10^6时，执行时间就已经不可接受了。

3. 数学优化解法深入解析

3.1 优化思路的来源

通过观察阶乘中5的分布规律，我发现可以分层次统计5的因子数量：

首先统计所有是5的倍数的数（贡献至少1个5）
然后统计所有是25的倍数的数（额外贡献1个5）
接着统计125的倍数，以此类推...

这实际上是一个数论问题：n!中质数p的幂次等于Σ[n/p^i]，其中i从1到∞。

3.2 优化算法实现

基于这个数学原理，可以写出极其简洁的代码：

typescript复制function trailingZeroes(n: number): number {
    let count = 0;
    while (n > 0) {
        n = Math.floor(n / 5);
        count += n;
    }
    return count;
};

算法执行过程示例（n=125）：

第一轮：125/5=25 → count=25
第二轮：25/5=5 → count=30
第三轮：5/5=1 → count=31
第四轮：1/5=0 → 结束

3.3 复杂度与正确性证明

这个算法的时间复杂度是O(log₅n)，因为每次n都除以5，直到n为0。对于n=10^9，最多只需要执行log₅(10^9)≈13次循环。

数学证明：

对于任意k，n/5^k表示有多少个数至少包含k个5因子
累加所有n/5^k就得到了总共有多少个5因子

4. 边界条件与特殊案例处理

4.1 边界条件考虑

在实际编码中，需要特别注意以下边界情况：

n=0：0!定义为1，应该返回0
n为负数：题目保证n>=0，但防御性编程可以考虑
大整数情况：虽然JS的Number有精度限制，但算法本身不会溢出

4.2 测试案例设计

完善的测试案例应该包括：

typescript复制console.log(trailingZeroes(5));    // 1
console.log(trailingZeroes(10));   // 2
console.log(trailingZeroes(25));   // 6
console.log(trailingZeroes(100));  // 24
console.log(trailingZeroes(1000)); // 249