172:阶乘后的零

2022-03-25  本文已影响0人  nobigogle

题意

给定一个整数 n ,返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

分析

阶乘后的0主要来源于2*5。

5*2  = 10
25 * 2 => 50 * 2 => 100
125 * 2 => 250 *2 => 500 *2 => 1000
// 得知5能贡献一个0,25能贡献2个0,125能贡献3个0

每个偶数部分都能分解出2。因此0的个数决定与能分解出5的个数。

题解

class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        long value = 5;
        while(n>=value){
            ans+=n/value;
            value = value*5;
        }
        return ans;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读