172. Factorial Trailing Zeroes.md

#172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

思路： 把数分解到最小的数的乘积，只有2*5才会产生0，而5的个数是显然小于2的个数的，所以找到所有5的个数就可以了。

对n!做质因数分解n!=2x3y5z*... 显然0的个数等于min(x,z)，并且min(x,z)==z 证明： 对于阶乘而言，也就是123*...*n [n/k]代表1~n中能被k整除的个数 那么很显然 [n/2] > [n/5] 左边是逢2增1，右边是逢5增1) [n/2^2] > [n/5^2]左边是逢4增1，右边是逢25增1) …… [n/2^p] > [n/5^p]左边是逢2^p增1，右边是逢5^p增1) 随着幂次p的上升，出现2^p的概率会远大于出现5^p的概率。 因此左边的加和一定大于右边的加和，也就是n!质因数分解中，2的次幂一定大于5的次幂 因此只需要要记录5的个数即可。但是需要注意的是：像25，125,625之类的数，除以5以后的结果还是5的倍数，所以还需要继续循环处理。

Java Solution(Iteration)

public class Solution {
    public int trailingZeroes(int n) {
        int count=0;
       while(n!=0){
           count+=n/5;
           n/=5;
       }
        return count;
    }
}

Java Solution(Recursion)

public class Solution {
    public int trailingZeroes(int n) {
        return n>=5? n/5 + trailingZeroes(n/5):0;
    }
}