题目描述

给定整数n，返回n!末尾0的个数。

要求对数时间复杂度。

样例

Example 1:

输入: 3
输出: 0
解释：3!=6，末尾没有0


Example 2:

输入: 5
输出: 1
解释：5!=120，末尾一个0

算法1

(质数分解) $O(log n)$

由于n!的后缀0是由起质因子2和质因子5相乘而来的，而2的个数总是比5多的，因此我们只需要计算n!中质因子5的个数即可。

要求n!中质因子5的个数即可，可以通过求$\sum{\frac{n}{5^i}}$而得。

例如，求245！末尾0的个数时，

245/5=49 代表着有49个数(可被$5$整除)贡献了1个5，

245/25=9 代表着有9个数(可被$5\times5$整除)在上一行的基础上多贡献了1个5，

245/125=1 代表着有1个数(可被$5\times5\times5$整除)在上一行的基础上多贡献了1个5，

像数字50在第一行被call过，在第二行也被call过，给target贡献了两个5，

所以245!末尾0的个数为49+9+1=59。

复杂度分析：

找一次$5^i$需要$O(1)$时间和$O(1)$空间，一共需要找$log_5n$次，所以时间复杂度是$O(log n)$，空间复杂度是$O(log n)$。

C++ 代码

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