tag 阶乘后0的个数
题目
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
思路
最容易想到的思路
如果阶乘后面有0，那么结果一定是10的倍数，进而一定是2和5的倍数，从而得到了这样的代码
public int trailingZeroes(int n) {
int twoNumber = 0;
int fiveNumber = 0;
for(int i = 0; i <n;i++) {
int k = i;
while(k % 2 == 0 || k % 5 == 0) {
if(k % 2 == 0) {
twoNumber++;
k /= 2;
}
if(k % 5 == 0) {
fiveNumber++;
k /= 5;
}
}
}
return twoNumber > fiveNumber ? fiveNumber : twoNumber;
}
将所有的数据从1到n（因为是n的阶乘）都过一遍，获取2和5的个数，并返回两个数个数最小的那个，这样才能组成10，但是这个算法对于大数会超时
第二种方法
也是我原来想不明白的，网上博客也是千篇一律，少了一个最重要的点。按照最容易的思路，还是要求2和5的倍数，但是由于阶乘的求法肯定是连着乘的，也就是1×2×3×4×5，你会发现只要出现5就一定会出现2，也就是网上博客说的只要统计5的个数就好了，那么关键点来了你统计谁的5的个数啊，是N还是N-1？这里要理解一个点，假设要求N的阶乘，那么我用会得到什么呢？，暂且把
记做m，那么就有
这个意思是说N是5的倍数，而m代表的是在其内部
中还会出现5的倍数，出现的个数为
个，也就是说m是求和后的5的总个数。为什么这么说呢，举个例子假设
那么
这样10中就是5的倍数，那么还会有
，那么5的倍数就是2个
除了5的倍数，还有25的不熟也会致使结果出现0也就是会出现N /= 5这个表达式的原因，例如就是N以内有m个25.
代码实现
public int trailingZeroes(int n) {
int ans = 0;
while(n > 0){
n /= 5;
ans +=n;
}
return ans;
}
