尾部的零

  |   分类   |   热度 ℃

前言

LintCode 是专注代码面试的在线评测系统，有很多代码题，可以用 Java、C++、Python 在线答题，我觉得还不错，就决定把做一做这些题，然后把题目的实现、优化思路写下来，一来是为了有更深的理解，二来是讨论一下还有没有更好的方法。

问题

LintCode：尾部的零

描述

设计一个算法，计算出n阶乘中尾部零的个数

样例

11! = 39916800，因此应该返回 2

挑战

O(logN)的时间复杂度

实现

问题分析

如果算出来阶乘再计算的话，至少要遍历一遍，肯定是无法达到 O(logN) 的时间复杂度的，所以要采用数学方法来解决。

例子：（1000的阶乘末尾0的个数，其中的“/”是取整除法）

$$
\begin{aligned}
&1000/5+1000/25+1000/125+1000/625\
=\quad&200+40+8+1\
=\quad&249(个)
\end{aligned}
$$

原理是：
假如你把 $1\times2\times３\times4\times\cdots\times N$ 中每一个因数分解质因数，结果就像：

$$1\times2\times3\times(2\times2)\times5\times(2\times3)\times7\times(2\times2\times2)\times\cdots$$

  • 10 进制数结尾的每一个 0 都表示有一个因数 10 存在——任何进制都一样，对于一个 M 进制的数，让结尾多一个 0 就等价于乘以 M 。
  • 10 可以分解为 $2\times5$ ——因此只有质数 2 和 5 相乘能产生 0 ，别的任何两个质数相乘都不能产生 0 ，而且 2 ，5 相乘只产生一个 0 。
  • 分解后的整个因数式中有多少对 $(2,5)$ ，结果中就有多少个 0 ，而分解的结果中，2 的个数显然是多于 5 的，因此，有多少个 5 ，就有多少个 $(2,5)$ 对。讨论 1000 的阶乘结尾有几个 0 的问题，就被转换成了 1 到 1000 所有这些数的质因数分解式有多少个5的问题。

$$10000 以内 0 的个数 = 5的倍数 + 5^2的倍数 + 5^3的倍数 + 5^4的倍数 + 5^5的倍数$$

代码实现 - C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
 public:
    // param n : description of n
    // return: description of return 
    long long trailingZeros(long long n) {
        long long temp = 5;
        long long result = 0;
        while(temp <= n){
            result += n / temp;
            temp *= 5;
        }
        return result;
    }
};

结果分析

5ms 完成，预想之中的快。

总结

数学思想忘得一干二净了，要加强数学思维才行。


本文整理自 淘气宝宝 的文章 求大数的阶乘和末尾0个数的计算
转载请注明原出处