题目链接：Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

这道题的要求是统计n!（n的阶乘）末尾有多少个0，要求对数时间复杂度。

既然要求对数时间复杂度，那么就不能从1到n都乘一下然后统计有多少0了。。。

找找规律吧！10可以产生1个0，25可以产生1个0，425可以产生2个0。。。以此类推，可以注意到，每出现1个5，就会产生1个0；每出现1个25，就会产生2个0；每出现1个125，就会产生3个0。。。也就是说，每出现1个5，就会多产生1个0；每出现1个25，就会多产生1个0；每出现1个125，就会多产生1个0。。。因此，我们只需统计n中包含多少个5、25、125等等，再把数量相加就是结果了。

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11

class Solution
{
public:
    int trailingZeroes(int n)
    {
        int res = 0;
        for(n /= 5; n != 0; n /= 5)
            res += n;
        return res;
    }
};

当然，递归的话，可以看到代码更简短，只剩下1行了。。。

1
2
3
4
5
6
7
8

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