面试题 16.05. 阶乘尾数

设计一个算法，算出 n 阶乘有多少个尾随零。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

---

分析质因子

考虑到因子2和5才有可能贡献尾数0，由于2一定比5多，只需考虑因子5的个数。

比如30，有30，25，20，15，10，5共6个数贡献7个因子5(25贡献了两个5)

一般通用情况下，考虑[1,n]中质因子p的个数。

[1, n]中p的倍数有n1=[n/p]个，即至少能贡献n1个质因子；

[1, n]中p^2的倍数有n2=[n/(p^2)]个，即至少能贡献n2个质因子；

举个例子，比如n=30, p=5, n1=[30/5]=6,也就是一阶5可以有6个贡献，即51，52，53，54，55，56
n2=[30/25]=1, 也就是二阶5有1个贡献，即25*1。

需要说明的是这里25虽然被计算了两次，但是却没有算重复，累积贡献2个5，其中一阶5和二阶5分别贡献了一次5。

由于5^3=125已经大于30了，所以就不用考虑三阶的5了。

推而广之，[1, n]中质因子的个数是
[n/p] + [n/(p^2)] + [n/(p^3)] + …

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

    }
};