lintCode题解(2)

标签（空格分隔）： lintCode

---

题目: 尾部的零

描述:

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

样例

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

挑战

O(logN)的时间复杂度

解析

这个问题其实就是从1到n这些数中，找出能够分解出多少对 2 和 5, 因为一对2x5就得出一个10.

我们发现从1开始每增加5个数就能分解出一个5，分别是 1x5，2x5，3x5，4x5，5x5...,
同时我们还发现每5个5的倍数就会额外的多分解出一个5例如5x5(多分解出1个5)，25x5(多分解出2个5)，125x5(多分解出3个5)...。我们发现这其实是关于5的幂的数。

如果我们能证明，只要我们能分解出一个5就必定能找到一个2与之相乘，则能分解出5的个数，就是尾部0的个数。这个证明是显然的。因为2比5小。

我们仔细分析上面的规律，n的阶乘中能分解出5的个数，其实就等于：能分解出多少个5的1一次幂的个数+能分解出5的2次幂的个数+能分解出5的3次幂的个数+...

例: 11！

• 5的1次幂的个数为2：5和10:实际上可以这样算11/5 = 2...1;(商即为结果)
• 5的2次幂的个数为0：没有。
• 所以11！中能分解出2对2x5，因此11！后面跟着2个0。

例：29！

• 5的1次幂的个数5：5，10，15，20，25.：计算方式29/5 = 5...4;(商即为结果)。
• 5的2次幂的个数1：25：计算方式29/(5的2次幂)=> 29/25 = 1...4;(商即为结果)。
• 所以29！中能分解出5+1 = 6对2*5，因此29！后面有6个0.

class Solution {
public:
    /*
     * @param n: A long integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    long long trailingZeros(long long n) {
        
        long long result = 0;
        
        while(n>0){
            result += n/5;
            n /= 5;
        }
        return result;
    }
};