题目

给定一个整数 n，返回 n! 末尾的 0 的个数。

注意：

你的算法的时间复杂度应该为 O(log n)。

难度：容易

编程语言：C++

分析

程序框架为：

class Solution {
public:
    int trailingZeroes(int n) {
        
    }
};

我们先列出 0 到 10 的阶乘，看能不能找出什么规律：

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000

可以看到：

0－4 的阶乘，末尾 0 的个数为 0
5－9 的阶乘，末尾 0 的个数为 1
10－14 的阶乘，末尾 0 的个数为 2
15－19 的阶乘，末尾 0 的个数为 3

看上面的规律，很明显就是

1
2
3

int trailingZeroes(int n) {
    return n / 5;
}

提交到 Leetcode，Wrong Answer。当 n = 30，正确应该返回 7，但我的程序返回 6。

题目当然不会这么简单了，我们回想一下九九乘法表，乘积末尾有 0 的，只有：

2 * 5 = 10
4 * 5 = 20
6 * 5 = 30
8 * 5 = 40

上面的 4 个乘积在末尾有一个 0。

那么为什么 30! 有 7 个 0？我们把 30! 展开：

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 * 21 * 22 * 23 * 24 * 25 * 26 * 27 * 28 * 29 * 30

要计算出 30! 末尾 0 的个数，我的思路是，展开式里的 5 的个数，就是 30! 末尾 0 的个数。30! 的 5 的个数是：

5
10，可分解为 2 * 5
15，可分解为 3 * 5
20，可分解为 4 * 5
25，可分解为 5 * 5
30，可分解为 6 * 5

共 7 个 5，而 1~30 里，肯定不止有 7 个 2、4、6、8（分解得出来的也包含）。那么问题转化为：求 n! 的展开式里 5 的个数。比较特殊的是 5 的幂，即 5^2 = 25，5^3 = 125。

以 30 为例，我设想的算法的执行过程是：

30 / 5 = 6，即一共有 6 个数是 5 的倍数
因为 30 > 25，所有 6 个数里面其中一个是 25，可分解为 2 个 5
所以一共有 7 个 5，返回

代码如下：

int trailingZeroes(int n) {
    int num5 = n / 5;
    // 遍历 n 以内的 5 的幂
    for (int i = 2; pow(5, i) <= n; i++) {
        num5 += i - 1;
    }
    return num5;
}

提交到 Leetcode，Wrong Answer。当 n = 50，正确应该返回 12，但我的程序返回 11。

那我们来把 50! 的 5 展开后得到：5, 10, 15, 20, 25, 30, 35, 40, 45, 50。因为 50 = 5 * 5 * 2，所以我的程序比正确答案少了一个 0。另外可以看到，所有 5 的倍数的数字，都可以 5 跟其它数字的乘积，而那个数又可以继续分解出 5 跟其它数字的乘积。如 100 = 5 * 20 = 5 * 5 * 4。我们又知道，一个数字，可以由一个唯一的的素数乘积所表示。所以现在的思路是，遍历 5 的倍数，把每个数都分解出 5 的乘积，从而统计所有 5 的个数。

代码如下：

#include <frequently-used-code-snippets.h>
class Solution {
public:
    int trailingZeroes(int n) {
        int num0 = 0;
        // 遍历 n 以内的 5 的倍数
        for (int i = 1; i * 5 <= n; i++) {
            int num5 = getNum5(i * 5);
            num0 += num5;
        }
        return num0;
    }
private:
    // 把 n 分解为 5 的乘积，返回 5 的个数
    int getNum5(int n) {
        int num5 = 0;
        while (n % 5 == 0) {  // 能整除 5，说明能分解一个 5 出来
            n /= 5;
            num5++;
        }
        return num5;
    }
};
int main() {
    Solution sol;
    cout << sol.trailingZeroes(30) << endl;
    cout << sol.trailingZeroes(50) << endl;
    cout << sol.trailingZeroes(200) << endl;
}
// 输出结果：
// 7
// 12
// 49

提交到 Leetcode，Time Limit Exceeded，导致超时的 n = 1808548329。

我们分析一下上面算法的时间复杂度。首先程序的第 9~12 行是一个 for 循环，用于遍历 n 以内所有的 5 的倍数。所以 for 循环的时间复杂度为 O(n / 5)，即 O(n)。另外在 for 循环里的 while 循环的时间复杂度是 O(log n)，所以整个程序的时间复杂度为 O(nlog n)，无法满足题目要求的 O(log n)。

我们再把 200! 里 5 的倍数的部分展开，看看 49 是如何计算出来的。

5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200。

可以看到：

1~200 里共有 40 个数是 5 的倍数，即是在 200! 里能分解出 40 个 5 的乘积。
接下来 40 / 5 = 8，表示这 40 个数里有 8 个是 25 的倍数，分别是 25, 50, 75, 100, 125, 150, 175, 200。即是在 200! 里能分解出 8 个 25 的乘积，即在步骤 1 的基础上能额外分解出 8 个 5 的乘积。
接下来 8 / 5 = 1，表示这 8 个数里有 1 个是 125 的倍数，即 125。即是在 200! 里能分解出 1 个 125 的乘积，即在步骤 1 的基础上能额外分解出 1 个 5 的乘积。

所以 5 的个数 = 40 + 8 + 1 = 49。那么代码很容易能写出来：

#include <frequently-used-code-snippets.h>
class Solution {
public:
    int trailingZeroes(int n) {
        int num5 = 0;
        for (int i = n / 5; i > 0; i /= 5) {
            num5 += i;
        }
        return num5;
    }
};
int main() {
    Solution sol;
    cout << sol.trailingZeroes(30) << endl;
    cout << sol.trailingZeroes(50) << endl;
    cout << sol.trailingZeroes(200) << endl;
}
// 输出结果：
// 7
// 12
// 49

提交到 Leetcode，Accepted! :) 运行时间为 3ms。

syawlaus

Leetcode 题解 - 172. Factorial Trailing Zeroes

题目

分析