【每日阅读】2020年10月15日-n!尾部有多少个零

真诚的希望您能留言与我交流,这会对我有非常大的帮助!

这是一道算法题,题目在这里:https://leetcode-cn.com/problems/factorial-trailing-zeroes/

有多少个零,其实就是算乘了多少个10,而乘了多少个10可以改为统计乘了多少个5。(2很多,因为偶数很多)

懂得了这个思路,其实代码就很简单。循环一遍所有乘数,然后逐一分析每个数最多可以分解出多少个5相乘,把这些5的个数相加,就是乘10的个数,就是尾部0的个数。

/**
 * 求n!结尾有多少个零
 */
public class ZeroCount {

    public static void main(String[] args) {
        for (int i = 1; i <= 10000; i++) {
            System.out.println(i + "!尾部有" + zeroCount(i) + "个零");
        }
    }

    /**
     * n返回n!尾部有多少个零
     */
    private static int zeroCount(int n) {
        int zeroCount = 0;

        for (int i = 1; i <= n; i++) {
            zeroCount += fiveCount(i);
        }

        return zeroCount;
    }

    /**
     * 返回有多少个因子5
     */
    private static int fiveCount(int num) {
        int r = num % 5;
        int fiveCount = 0;

        while (r == 0 && num >= 5) {
            fiveCount++;
            num /= 5;
            r = num % 5;
        }

        return fiveCount;
    }

}
【每日阅读】2020年10月15日-n!尾部有多少个零插图(1)

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/2595

发表评论

电子邮件地址不会被公开。 必填项已用*标注

GitHub
分享本页
返回顶部