LeetCode172. Factorial Trailing Zeroes

172.Factorial Trailing Zeroes

题意：

Given an integer n, return the number of trailing zeroes in n!.
给定一个正整数n，返回 n！的末尾的 0 的个数。
Note: Your solution should be in logarithmic time complexity.

我的想法：

就只想到了用暴力求解，先求出阶乘的值，再看这个值的末尾有几个0.
很显然不符合题目要求，果然运行超时未通过。

public int trailingZeroes(int n) {
    int res = 0;
    int ans = 1;
    for(; n > 0; n--){
        ans *= n;
    }
    while(ans % 10 == 0){
        res++;
    }
    return res;
}

进一步发现：

每出现一个5,10,15,20，阶乘的末尾就会多出1个0。
然后直接返回了return n/5;
报错，当输入为25时，输出应为6；
这是因为5,10,15,20中各有一个5，而25中有两个5；

最终：

这里我们要求n!末尾有多少个0，因为我们知道0是2和5相乘得到的，而在1到n这个范围内，2的个数要远多于5的个数，所以这里只需计算从1到n这个范围内有多少个5就可以了。
* 假如i可以被5整除，则可以提供的5的个数为i/5个;
* 假如i可以被25整除，则可以多提供的5的个数为i/25个;
* 假如i可以被125整除，则可以多提供的5的个数为i/125个（算上了被5，25整除之后）;

所以除了计算n/5， 还要计算n/5/5, n/5/5/5, n/5/5/5/5, ..., n/5/5/5,,,/5直到商为0.

public int trailingZeros2(int n){
    int res = 0;        
    while(n != 0){
        n = n / 5;
        res += n;
    }
    return res;
}