By

文章目录
  1. 1. 思路
  2. 2. 证明
  3. 3. 解法 1
  4. 4. 解法 2
  5. 5. 总结

来自LeetCode的第172道算法题Factorial Trailing Zeroes：

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

即给一个整数 n, 给出 n 的阶乘 n! 中有多少个 0，要求算法时间复杂度是 O(log(n))

思路

看到题目后，有人直接拔“刀”切“菜”，先 ‘％’ 再 ‘/‘ ，各种挥舞之后，发现提示 “Out of Range” 的错误，然后绞尽脑汁，回忆各种数据结构与算法，尝试是否能够尽快“吞”下，最后发现还是被“噎”住了:(

要拿下这个题目，要考验基本数学功底了。。。看了网上许多分析解决的思路，觉得陆草纯的分析很透彻，思路原来酱紫的。

证明

对 n! 做质因数分解 n! = 2^x * 3^y * 5^z * ...

由于所有的质因数中，只有2 * 5 得到的结果中才会有 0 出现，因此，只需要根据质因数 2 或 5 的幂次就可以知道 0 的个数了，那么，到底是 2 的幂次，还是 5 的幂次才是 0 出现的个数呢？

显然 0 的个数等于 min(x, z)，并且 min(x, z) == z

对于阶乘而言，也就是1 * 2 * 3 * ... * n

[n/k] 代表 1 ~ n 中能被 k 整除的个数

那么很显然

[n/2] > [n/5] (左边是逢2增1，右边是逢5增1)

[n/2^2] > [n/5^2](左边是逢4增1，右边是逢25增1)

...

[n/2^p] > [n/5^p](左边是逢 2^p 增1，右边是逢 5^p 增1)

随着幂次p的上升，出现2^p的概率会远大于出现2^p的概率。

即 2 的各个幂次的加和一定大于 5 的各个幂次的加和，也就是 n! 质因数分解中，2 的次幂一定大于 5 的次幂；）

解法 1

1
2
3
4
5
6
7
8
9
10
11
12
13
int trailingZeroes(int n) {
    int ret = 0;

    for(int i = 1; i <= n; i ++) {
        int tmp = i;
        while(tmp % 5 == 0) {
            ret++;
            tmp /= 5;
        }
    }

    return ret;
}

解法1还有优化的空间…….

解法 2

根据上面的证明过程分析可以看出，起作用的只有被5整除的那些数。能不能只对这些数进行计数呢？

存在这样的规律：[n/k] 代表 1~n 中能被 k 整除的个数。有一点要注意的就是25这种，5和5相乘的结果，所以，还要看 n/5 里面有多少个5，也就相当于看n里面有多少个25，还有125，625…..

1
2
3
4
5
6
7
8
9
10
int trailingZeroes(int n) {
    int ret = 0;

    while(n) {
        ret += n / 5;
        n /= 5;
    }

    return ret;
}

看到解法2这么简洁优美的代码，我已经醉了…

总结

数学功底很关键，很重要！

突然想到“我是歌手3”里歌手李健看到数字 2 后，第一个反应是 “2 是质数里面的第一个啊，挺好的”，也是醉了；）

文章目录
  1. 1. 思路
  2. 2. 证明
  3. 3. 解法 1
  4. 4. 解法 2
  5. 5. 总结