README.md

题目

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

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

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

说明: 你算法的时间复杂度应为对数级

解答

10=2*5，因此，每一对(2,5)就可以产生一个0

由于每个偶数中就可以分解出一个因子2，因此n!中，2的个数肯定比5多，所以问题转换为求1~n中，可以分解出多少个因子5：

5,10,15,20,25,30,...,125,130,...

因此，n/5就可以就得有多少个数能分解出1个5

但是注意上面的25和125：

25 = 5 * 5;
125 = 5 * 5 * 5;

这些数中可以分解出多个5，因此，还需要求1~n中，能分解出多少个25，125...

25,50,75,100,125,150,...
//等价于1*(5*5),2*(5*5),3*(5*5),...,5*(5*5),...，这些数中的5还需要加1次

125,250,375,...
//等价于1*(5*5*5),2*(5*5*5),3*(5*5*5),...，这些数中的5又要多加1次

...

故，设num=5，每次累加n/num后，num就需要乘以5。知道num>n：

class Solution {
public:
    int trailingZeroes(int n) {
        long long num = 5;
        int count = 0;
        while(num <= n){
            count += (n / num);
            num *= 5;
        }
        return count;
    }
};

注意，num的类型为long long，原因在于使用int时可能溢出，例如：

当 n = 1808548329时，如果num为int，在num>n之前，num的值：

5
25
125
625
3125
15625
78125
390625
1953125
9765625
48828125
244140625
1220703125
1808548329       //这里开始溢出
452807053
-2030932031
-1564725563
766306777
-463433411

INT_MAX:2147483647