Factorial Trailing Zeroes -- leetcode

Factorial Trailing Zeroes -- leetcode

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

Note: Your solution should be in logarithmic time complexity.

基本思路：

統計n!尾數0的個數。

尾數0則是由因子2，5 乘積得來的。

要統計0的個數，則需要統計2，5的因子個數。 由於2的數量比5多，故只需要統計5的因子個數。

比如 5, 10, 15, 15, 20 n * 5， 含有一個5.

25, 50, 75, n * 25, 含有2個5。

n * 125 含有3個5。

。。。

由於後者，與前者有交集，被前者已經統計過。故只需要額外再對後者加一次即可。

return n/5 + n/25 + n/125 + n/625 + n/3125+...;

或者寫作：

n/5 + (n/5)/5 + (n/5/5)/5 + (n/5/5/5)/5

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