一道很简单不过有点绕的题(也可能是我渣)
给一个数n,求n! 中末尾0的个数。
第一个想法:O(n) 从1 到n 累加每个数中包含的2 的个数 和 5 的个数,最后输出较的数,很简单粗暴的算法,本来以为水个简单题妥妥的,结果居然T了(T T)
O(n)复杂度的过不去,就要想数学的方法了,由于2的数目肯定比5 多,直接统计从1到n中的数中包含多少个质因数5就行,
开始饶了很多,想单独处理5的次方项什么的,麻烦的要死。后来发现几行代码就可以搞定了:
class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while(n != 0){
n = n / 5;
ans = ans + n;
}
return ans;
}
};
从1 到 n ,先除第一个5,得到的就是所有5的倍数的个数,把这个数记下来
再除第二个5,得到的就是所有25的倍数的个数,他们每个包含至少2个5,但是之前依旧都记过一次了,这里也只记1一次
依次类推,直到除到0为止,这样累加的结果就是我们要求的。