2. 尾部的零

描述

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

样例

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

挑战

O(logN) 的时间复杂度

思路
问题：N的阶乘(N!)中的末尾有多少个0?
例如:N = 5, N ! = 120.末尾有1个0.

分析:想到这个问题，有人可能第一反应就是现求出N!,然后再根据求出的结果，除10来计算，最后得出N!的末尾有多少个0。但是转念一想，会不会溢出，超时等等。

其实，从"哪些数相乘可以得到10"这个角度，问题就变得比较的简单了。
首先考虑，如果N的阶乘为K和10的M次方的乘积，那么N!末尾就有M的0。如果将N的阶乘分解后，那么
N的阶乘可以分解为： 2的X次方，3的Y次方，5次Z方，.....的乘积。由于10 = 2 * 5,所以M只能和X和Z有关，每一对2和5相乘就可以得到一个10，于是M = MIN(X,Z),不难看出X大于Z，因为被2整除的频率比被5整除的频率高的多。所以可以把公式简化为M=Z.

由上面的分析可以看出，只要计算出Z的值，就可以得到N!末尾0的个数
方法一
要计算Z，最直接的方法就是求出N的阶乘的所有因式(1,2,3,...,N)分解中5的指数。然后求和。
方法二：
Z = N/5 + N /(55) + N/(555).....知道N/(5的K次方)等于0
公式中 N/5表示不大于N的数中能被5整除的数贡献一个5，N/(55)表示不大于N的数中能被25整除的数再共享一个5.......

代码

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