菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
420
0

172. 阶乘后的零

原创
05/13 14:22
阅读数 27581

 

 

我们知道10=5*2,那么末尾0的个数实际上就是看2和5出现的次数,因为

只要是偶数就可以拆分成2*x,2的出现次数必然高于5,所以实际上结果

是由5的出现次数决定的。

比如25的末尾零=(1*5)(2*5)(3*5)(4*5)(5*5),在对5取余后由于25=5*5,所以实际上还有一层5,

由此可知,我们除了要计算5的个数,还需要计算25,125等5的次方出现的个数。

于是我们可以循环取模计算。

时间O(log5N)(不停对5去模),空间O(1)

    public int trailingZeroes(int n) {
        int res=0;
        while(n>0){
            // 循环递推5的阶乘
            n=n/5;
            res=res+n;
        }
        return res;
    }

 

发表评论

0/200
420 点赞
0 评论
收藏
为你推荐 换一批