讨论/《春招冲刺班 - 7 天刷题挑战》 - 172. 阶乘后的零/
《春招冲刺班 - 7 天刷题挑战》 - 172. 阶乘后的零
共 10 个回复
  • 2 * 5 = 10,才会在末尾贡献 0
  • 答案为 n! 中因子 2 的数量和因子 5 的数量的最小值
  • 阶乘中因子 5 的数量一定小于因子 2 的数量
  • 先从 1 - n 中的: 1 * 5, 2 * 5, ..., x * 5 每个拿出一个因子 5,有 x = n / 5 个数可以拿出
  • 拿完后剩下 1, 2, 3, ..., x; 重复上一步
class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0){
            count += n / 5;
            n /= 5;
        }
        return count;
    }
}
23

0的贡献来源于:本身有0,或是偶数与5的倍数相乘获得;
1、由于偶数的个数一定比5的倍数的个数多,因而对于这种情况只考虑5的倍数的个数
2、本身有0的数恰好是5的倍数,拥有的0的个数恰好又与是5^n的倍数的n相等
综上,只需要计算阶乘中各个5的次方数的个数和即可。【因为是多少次方就会在其中被计算多少次,因而不需要考虑是否会有重复计算的问题】
代码如下:

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while(n >= 5){
            n = n / 5;
            count += n;
        }
        return count;
    }
}
3

参与“7天刷题挑战”的童鞋欢迎点击问卷加入专属社群哦~
2月1日-7日,字节跳动工程师直播刷题等你来围观

1

阶乘质因子

class Solution {
public:
    int trailingZeroes(int n) {
        int s5=0,s2=0;
        int tn=n;
        while(tn) s5+=tn/5,tn/=5;
        tn=n;
        while(tn) s2+=tn/2,tn/=2;
        return min(s5,s2);
    }
};
class Solution:
    def trailingZeroes(self, n: int) -> int:
        #每2*5贡献一个0   统计1-n含2  5因子的个数
        #因为n!中偶数肯定比5的倍数多   所以对数由较少的5的倍数决定
        #1-n中有多少数是5的倍数呢? 例如125    125/5=25   25?  不对是31
        #对于25 125   25=5*5  实际上是可以拆分出2个5的
        #故实际是1-n中找5的x次方的倍数
        res=0
        while n:
            res+=n//5
            n//=5
        return res
        


补充一下我的相仿
只有5的倍数才有5

所有 n/5 相当于求 < n的数中有多少个是5的倍数

为什么是n/5

仔细审题,发现尾数的零都是由因数含有5的元素贡献的,若某元素E 满足:

5aba,b均为正整数)②E<n①5^a*b(a,b均为正整数) ②E < n

则E和符合条件的若干偶数相乘(一个5和2相乘即可为尾数增添一个0)即可得到尾数带有a个0的结果。

对于数字n,第一轮我们先算因数包含5的元素个数,有几个元素则尾数就有几个0;

第二轮再看因数包含25的元素个数,有c个元素则尾数就有2*c个0(25 = 5×5);

第三轮再看因数包含125的元素个数,有c个元素则尾数就有3*c个0(125 = 5×5×5)

以此类推,直到包含5的a次方因数的元素为0即停止,要注意的是,每轮计算中有重复前面计算的部分,因此实际上每轮增加的0的个数均为元素数,因此最后将每轮的元素数相加即可。

代码

public class Solution {
    public int trailingZeroes(int n) {
        int number = 0;
        int consult = 0;//商,即每轮元素个数
        int count = 1;
        do{
            int divisor = (int)Math.pow(5, count);
            consult = n/divisor;
            number += consult;
            count++;
        }while(consult!=0);

        return number;
    }
}
/**
 * @param {number} n
 * @return {number}
 */

// 0 由 2*5 产生, 2作为因数出现的次数远大于5
// 所以我们需要找到 n! 中所有作为因素的5

// 计算的是 n!的0, 实际上就是计算 n! 中有几个5参与运算

// 1 2 3 2*2 5 2*3 7 2*2*2*2 3*3 2*5
// 比如 10! 中 5(1*5)和10(2*5), 有两个数字参与运算

// 问题转化为 1-10中 有几个数是5的倍数, 而5的倍数需要满足 5或10结尾
// 所以我们可以通过 n/5 来获得所有5的倍数

// 但是仅仅如此还不够, 遇到25的情况下, 25/5=5 , 剩下的数字中还存在5的倍数
// 当我们遇到5*5, 5*5*5 的时候, 所以还需要判断25的倍数, 125的倍数...

var trailingZeroes = function(n) {
    let count = 0;
    while (n > 0){
        count += Math.floor(n / 5);
        n /= 5;
        n = Math.floor(n)
    }
    return count;
};

解释的太棒了