博客

Leetcode每日一题：

172. 阶乘后的零

题目：

给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：
输入：n = 0
输出：0

提示：
0 <= n <= 104

思路：

其实是数学问题：能产生0的是5和10，其实10也是因为包含质数5，5的质数比2的质数多

只需要统计所有质数5的个数即可（方法1）

优化是减少重复计算（方法2）

代码

 /**
     * 方法1：
     * 遍历N，对每个数字包含的5的质数个数进行统计
     *
     * @param n
     * @return
     */
    public static int trailingZeroes(int n) {
        int res = 0;
        for (int i = 5; i <= n; i++) {
            int curNum = i;
            while (curNum != 0 && curNum % 5 == 0) {
                res++;
                curNum = curNum / 5;
            }
        }
        return res;
    }

    /**
     * 方法2：
     * 前面包含了很多重复计算，减少重复统计
     *
     * @param n
     * @return
     */
    public static int trailingZeroes1(int n) {
        int res = 0;
        while (n > 0) {
            n /= 5;
            res += n;
        }
        return res;
    }