描述

設(shè)計(jì)一個(gè)算法，計(jì)算出n階乘中尾部零的個(gè)數(shù)

樣例

11! = 39916800，因此應(yīng)該返回 2

挑戰(zhàn)

O(logN) 的時(shí)間復(fù)雜度

思路
問(wèn)題：N的階乘(N!)中的末尾有多少個(gè)0?
例如:N = 5, N ! = 120.末尾有1個(gè)0.

分析:想到這個(gè)問(wèn)題，有人可能第一反應(yīng)就是現(xiàn)求出N!,然后再根據(jù)求出的結(jié)果，除10來(lái)計(jì)算，最后得出N!的末尾有多少個(gè)0。但是轉(zhuǎn)念一想，會(huì)不會(huì)溢出，超時(shí)等等。

其實(shí)，從"哪些數(shù)相乘可以得到10"這個(gè)角度，問(wèn)題就變得比較的簡(jiǎn)單了。
首先考慮，如果N的階乘為K和10的M次方的乘積，那么N!末尾就有M的0。如果將N的階乘分解后，那么
N的階乘可以分解為： 2的X次方，3的Y次方，5次Z方，.....的乘積。由于10 = 2 * 5,所以M只能和X和Z有關(guān)，每一對(duì)2和5相乘就可以得到一個(gè)10，于是M = MIN(X,Z),不難看出X大于Z，因?yàn)楸?整除的頻率比被5整除的頻率高的多。所以可以把公式簡(jiǎn)化為M=Z.

由上面的分析可以看出，只要計(jì)算出Z的值，就可以得到N!末尾0的個(gè)數(shù)
方法一
要計(jì)算Z，最直接的方法就是求出N的階乘的所有因式(1,2,3,...,N)分解中5的指數(shù)。然后求和。
方法二：
Z = N/5 + N /(55) + N/(555).....知道N/(5的K次方)等于0
公式中 N/5表示不大于N的數(shù)中能被5整除的數(shù)貢獻(xiàn)一個(gè)5，N/(55)表示不大于N的數(shù)中能被25整除的數(shù)再共享一個(gè)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;
    }
};