172. Factorial Trailing Zeroes

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

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

---

本题要求n的阶乘结果中末尾有多少个数字0。暴力方法就是先把n!求出来，然后不断除10算末尾0的个数，但是暴力方法无法满足log(n)的时间复杂度。 参考网上的题解：http://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/，分析得还是很详细的。 要产生一个尾数0，必须是10=2*5，所以算n!中min(2的素因子，5的素因子），就有多少个0。简单考察一下5!= (2 * 2 * 2 * 3 * 5)，11!= (2 ⁸ * 3⁴ * 5² * 7)，即n!中2的素因子个数肯定要比5的素因子个数要多，这个也是可以证明的。比如从5k+1到5(k+1)，只多了一个5的素因子， 但是[5k+1, 5k+2]至少多了一个2的素因子，从[5k+3, 5k+4]又至少多了一个2的素因子。所以2的素因子要多于5的素因子。
下面就把问题转换为求n!中5的素因子的个数。

举一个例子20!=1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20，能够分解出5的素因子的数只有5,10,15,20，一共4=floor(20/5)。所以20!=2432902008176640000有4个尾数0。所以n!中5的素因子的个数是floor(n/5)？

且慢，如果n=25，floor(n/5)=5，但是25=5*5能分解出两个5的素因子，所以25!中应该有六个5的素因子。所以每增加一个25的倍数的数，5的素因子的个数加1；同理每增加一个125的倍数的数，5的素因子要加2，但因为125的倍数的数肯定是25的倍数的数，所以我们在求25的倍数的数的时候已经求过一次125倍数的数的个数了，结果就是5的个数=floor(n/5)+floor(n/25)+floor(n/125)+…
完整代码如下，注意i要是long long类型的，否则可能溢出。

class Solution {
public:
    int trailingZeroes(int n)
    {
        int ans = 0;
        for (long long i = 5; n / i >= 1; i *= 5) {
            ans += n / i;
        }
        return ans;
    }
};

本代码提交AC，用时3MS。
还有一种解法，思路是一样的：

class Solution {
public:
    int trailingZeroes(int n)
    {
        int ans = 0;
        while (n > 0) {
            ans += n / 5;
            n /= 5;
        }
        return ans;
    }
};

第一种解法是固定分子不变，第二种解法是固定分母不变，结果是一样的。