数学优化算法题

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

例子：输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零.

解法一：暴力解，朴实无华

拿到这个题，我第一反应就是最简单的思路：先把 n 的阶乘算出来，然后看它末尾有几个 0。这思路没毛病，非常直接。

怎么算末尾有几个 0 呢？就是一个数不停地除以 10，直到不能整除为止，看总共除了多少次。

来，上代码。

import java.math.BigInteger;

class Solution1 {
    public int trailingZeroes(int n) {
        // n! 可能会非常大，int 和 long 肯定会溢出，所以得用 BigInteger
        BigInteger nFactorial = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            nFactorial = nFactorial.multiply(BigInteger.valueOf(i));
        }

        // 开始计算末尾有多少个 0
        int zeroCount = 0;
        // 只要这个数能被 10 整除，就继续
        while (nFactorial.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
            zeroCount++;
            nFactorial = nFactorial.divide(BigInteger.TEN);
        }
        return zeroCount;
    }
}

这代码咋一看，逻辑清晰，实现简单。但是，停！这里面有个巨大的坑。

n! 的增长速度是超乎想象的。当 n 稍微大一点，比如 n=20，20! 就已经是一个非常大的数了（2,432,902,008,176,640,000），long 类型都存不下。虽然我们用了 BigInteger 救场，但当 n 更大，比如 10000 呢？BigInteger 的乘法和除法运算都会变得非常非常慢。

这个解法，在 n 比较小的时候还行，一旦 n 的规模上来，立马超时。面试官要是看到这个解法，肯定会接着问：“有没有更好的方法？这个方法有什么问题？”

所以，暴力解法只是我们思考的起点，用来验证我们对题目的理解。它能 work，但不够好。

解法二：思维小跳跃，寻找规律

暴力解法的问题在于我们去“计算结果”，然后从结果里找答案。但很多时候，答案的规律隐藏在“计算过程”中。

我们回过头想，末尾的 0 是从哪来的？

10 来的。120 = 12 * 10。 1200 = 12 * 100 = 12 * 10 * 10。

一个末尾的 0，就意味着这个数有一个因子 10。两个 0，就是有两个因子 10。

那因子 10 又是从哪来的？

10 = 2 * 5。

一个 10 必须由一个 2 和一个 5 相乘得来。所以，n! 的结果末尾有多少个 0，就取决于 n! 的所有质因数分解后，能凑出多少对 (2, 5)。

好，问题转化了：计算 n! 的质因数分解中，2 的个数和 5 的个数，然后取其中较小者。

我们来看 n! 的计算过程：1 * 2 * 3 * 4 * 5 * ... * n。我们把这些数全部进行质因数分解，然后统计 2 和 5 的总数。

举个例子，10! = 1 * 2 * 3 * (2*2) * 5 * (2*3) * 7 * (2*2*2) * (3*3) * (2*5)

我们来数一下：

因子 2 的来源：2, 4(两个2), 6, 8(三个2), 10。总共有 1 + 2 + 1 + 3 + 1 = 8 个 2。
因子 5 的来源：5, 10。总共有 1 + 1 = 2 个 5。

能凑出 min(8, 2) = 2 对 (2, 5)。所以 10! 的末尾应该有两个零。我们算一下 10! = 3,628,800。果然是两个零！

这个思路挺好。而且我们很快会发现一个规律：在 n! 的质因数分解中，因子 2 的数量永远比因子 5 的数量多。

为啥？因为每隔 2 个数就有一个偶数（提供因子2），而每隔 5 个数才有一个数提供因子 5。提供 2 的频率远高于 5。

所以，瓶颈就在 5 的数量上。问题再次被简化：计算 n! 的质因数分解中，因子 5 的数量有多少个。

怎么算呢？我们可以遍历从 1 到 n 的所有数字，对每个数字，我看它能贡献多少个因子 5。

比如 i = 5，贡献一个 5。 i = 10 (即 2*5)，贡献一个 5。 i = 25 (即 5*5)，贡献两个 5。 i = 30 (即 2*3*5)，贡献一个 5。

代码就来了：

class Solution2 {
    public int trailingZeroes(int n) {
        int fiveCount = 0;
        for (int i = 1; i <= n; i++) {
            int current = i;
            // 检查 current 这个数本身包含多少个因子 5
            while (current > 0 && current % 5 == 0) {
                fiveCount++;
                current /= 5;
            }
        }
        return fiveCount;
    }
}

这个方法怎么样？我们彻底告别了 BigInteger，避免了溢出问题。时间复杂度是 O(N logN) 这个级别（内层 while 循环是 log 级别），虽然 n 大了还是会慢，但比暴力解法已经强了不知道多少个数量级了。这是一个非常大的进步，面试到这一步，说明你已经有不错的分析能力了。

但这还不是最优解。

解法三：终极优化，数学之美

解法二的循环 for (int i = 1; i <= n; i++) 还是不够快。我们是在对每个数 i 分解，再累加。能不能换个角度，直接计算总共有多少个因子 5 呢？

我们想，在 1 到 n 的所有数里：

有多少个数是 5 的倍数？它们至少能提供一个因子 5。这些数是 5, 10, 15, 20, 25, ...。它们的数量是 n / 5。
但是，像 25, 50, 75, ... 这些数，它们是 25 的倍数，可以提供 至少两个 因子 5。在第一步里，我们只统计了它们提供的一个 5。所以，我们得把它们提供的第二个 5 也加上。 25 的倍数有多少个？n / 25。
同理，像 125, 250, ... 这种 125 的倍数，可以提供 至少三个 因子 5。 125 = 5 * 5 * 5。在第一步，我们算了第一个 5。在第二步，我们算了第二个 5。现在，我们得把第三个 5 加上。 125 的倍数有多少个？n / 125。
...以此类推。

所以，总的因子 5 的数量就是： count = (n/5) + (n/25) + (n/125) + ... 直到 n/5^k 等于 0。

这个公式看起来是不是特别清爽？

比如 n = 100。

5 的倍数有 100 / 5 = 20 个。
25 的倍数有 100 / 25 = 4 个。
125 的倍数有 100 / 125 = 0 个。
总的因子 5 的数量就是 20 + 4 = 24 个。所以 100! 末尾有 24 个零。

这个算法，把 O(N) 级别的遍历，直接降到了 O(logN) 级别。这才是这道题想考察的最终解法。

代码实现起来也异常简洁：

class Solution3 {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
}

你看这个代码，是不是感觉有点神奇？它其实就是 count += n/5; count += n/25; ... 的一个精巧实现。第一次循环，n 变成 n/5，count 加上了 n/5。第二次循环，n 变成了 (n/5)/5 = n/25，count 又加上了 n/25。以此类推，完美！

总结一下

这道题的解题过程，其实是一个思维不断提升的过程：

暴力解法：最直观，但有严重的性能和溢出问题。它模拟了“我们手工怎么算”，但计算机不应该这么笨。
因子分析法：从问题本质入手，将“数末尾的0”转化为“找因子(2,5)对”，再简化为“找因子5”。这是一个巨大的思维飞跃，从关注“结果”转向关注“过程和成因”。
数学优化法：在解法二的基础上，再次转变计算思路。从“一个个地数每个数贡献了几个5”，变为“一批批地数有多少个数能贡献5”。这种批处理、宏观统计的思路，是算法优化中常见的利器。

从 BigInteger 乘除法的 O(N^2) 级别，到 O(NlogN)，再到最终的 O(logN)，我们一步步剥开问题的外壳，触及它的数学核心。这，就是算法的魅力所在。