描述
設(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;
}
};
