首页 > 其他 > 详细

计算出n阶乘中尾部零的个数

时间:2020-06-03 14:04:51      阅读:47      评论:0      收藏:0      [点我收藏+]

题目: 设计一个算法,计算出n阶乘中尾部零的个数 

例子: 

输入:  6
输出:  1
    
样例解释:
6! = 720, 结尾的0有1个。

思路:

最简单暴力的方法就是直接把数的阶乘计算出来,然后数这个末尾有几个0。

public long trailingZeros(long n) {
        long result = 1l;
        for (long i = 1; i <= n; i++) {
            result = i * result;
        }
        String resultStr = result + "";
        int index = resultStr.length() - 1;
        int zeroNumber = 0;
        while (resultStr.charAt(index) == ‘0‘) {
            zeroNumber++;
            index--;
        }
        return zeroNumber;
    }

延伸:

在小数的阶乘时上面的暴力法一点问题没有。但当是大数时,阶乘就会出现问题,计算量和内存都会浪费很多。

那我们是否有更优雅的方式呢?

我们寻找其中的规律可以发现,0的产生是和2和5有关的,为什么不是4和5、8和5,因为2和5是最小不能再小的相关数字。那实际上我们只需要计算有多少个5就可以得到结果了。

代码如下:

public long trailingZeros(long n) {
        long sum = 0;
        while (n != 0) {
            sum += n / 5;
            n /= 5;
        }
        return sum;
    }

计算出n阶乘中尾部零的个数

原文:https://www.cnblogs.com/zh-ch/p/13036652.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!