阶乘后的零

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;
    }