Description
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
Solution
蠻有趣的題目揉稚。細(xì)細(xì)想來嫌拣，10分解成質(zhì)數(shù)就是2*5，每個0都需要一對2和5來造成：
n! = 2^x * 5^y * … where x and y >= 0
很明顯，x >= y即舌，只需計(jì)算y即可嘲叔。
那么5的個數(shù)如何計(jì)算呢奠支？對于每個k來說晕讲，需要計(jì)算它由幾個5組成。注意墩新，并不是只有5的冪才會出現(xiàn)多個5贸弥，像50里面就有兩個5！
5=1*5, 10=2*5, 15=3*5, 20=4*5, 25=5*5, 30=6*5 ... , 50=10*5=2*5*5
result = (1到n中被5^1整除的個數(shù)) + （1到n中被5^2整除的個數(shù)）+ ... + （1到n中被5^m整除的個數(shù)）
就可以用遞歸的思路啦海渊，1到n中被5^1整除的個數(shù)即n / 5茂腥。
class Solution {
public int trailingZeroes(int n) {
int zeroes = 0;
while (n > 0) {
n /= 5;
zeroes += n;
}
return zeroes;
}
}
