题目描述
题解
\(n!\) 中尾随0的个数等于 \(n!\) 中因子10的个数，而10=2 * 5，所以转化为求 \(n!\) 中因子2和因子5的较小数。显然，质因子5的个数不会大于2的个数，因此只需求 \(n!\) 中质因子5的个数。更为一般的，我们对[1,n]中的各个数分解质因数，分析能分析多少个质因数 \(p\).
我们定义 [ ] 为向下取整运算，那么:
\([1,n]\) 中能够分解出至少1个质因数 \(p\) 的个数为 \(x_1=[\frac{n}{p}]\)
\([1,n]\) 中能够分解出至少2个质因数 \(p\) 的个数为 \(x_2=[\frac{n}{p^2}]\)
...
\([1,n]\) 中能够分解出至少 \(k\) 个质因数 \(p\) 的个数为 \(x_k=[\frac{n}{p^k}]\)
其中，\(k\) 需要满足 \(p^k \le n\)，而且，上面每一类数均是前一类数的子集。
本题中，\(n!\) 中质因子2的个数为 \(\sum_{i=0}^{k1}[\frac{n}{2^i}]\).
\(n!\) 中质因子5的个数为 \(\sum_{i=0}^{k2}[\frac{n}{5^i}]\)
可以发现质因子5的个数不会多于质因子2的个数，因此只需统计5的个数，代码如下
class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while (n) {
n /= 5;
ans += n;
}
return ans;
}
};
时间复杂度 \(O(logn)\)