当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.172.Factorial Trailing Zeroes 阶乘后的零

LeetCode.172.Factorial Trailing Zeroes 阶乘后的零

题目描述

172 Factorial Trailing Zeroes
https://leetcode-cn.com/problems/factorial-trailing-zeroes/

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in O(logn) time complexity.


解题过程

题目要求 O(logn) 时间复杂度,所以肯定得用一个类似二分的方法。

n 的阶乘末尾 0 的个数就是看 n! 是 10 的多少倍,注意到 2 × 5 也会得到一个 10,所以是看 n! 中有多少个 5
1, 2, 3, … , n 序列中,每隔 5 个数就会遇到一个 5 的倍数,所以看 n 是 5 的多少倍(向下取整)就能知道 n! 中有多少个 5
但是! 每隔 5 × 5 = 25 个数,会遇到一个 25 的倍数,比如 25, 50, 75…,这些 25 的倍数会给 n! 中贡献 2 个 5
同理,每隔 5 × 5 × 5 = 125 个数,会遇到一个 125 的倍数, 给 n! 中贡献 3 个5
所以,我们要统计 n 是 5 的多少倍,加上 n 是 5^2 = 25 的多少倍,加上 n 是 5^3 = 125 的多少倍,加上 n 是 5^i 的多少倍。

因为我们统计倍数的因子 5^i 是指数增长的,所以时间复杂度是 O(logn)

第一个实现方法 trailingZeroes() 中,five 必须用 long,否则随着 five 变量不断增大会溢出 int 导致变为负值,进而多统计。
第二个实现方法 trailingZeroes2() 中,改为 n 不断除以 5 变小,没有溢出风险

private static class SolutionV2020 {
    public int trailingZeroes(int n) {
        long five = 5;
        int zeroCount = 0;
        while (five <= n) {
            zeroCount += n / five;
            five *= 5;
        }
        return zeroCount;
    }

    public int trailingZeroes2(int n) {
        int zeroCount = 0;
        while (n != 0) {
            zeroCount += n / 5;
            n /= 5;
        }
        return zeroCount;
    }
}

public static void main(String[] args) {
    SolutionV2020 solutionV2020 = new SolutionV2020();
    System.out.println(solutionV2020.trailingZeroes(3));
    System.out.println(solutionV2020.trailingZeroes(5));
    System.out.println(solutionV2020.trailingZeroes(11));
    System.out.println(solutionV2020.trailingZeroes(25));
    // 易错用例,正确结果是 452137076, 如果 five 变量用 int 会溢出变为负值导致多统计了2个5得到错误结果 452137078
    System.out.println(solutionV2020.trailingZeroes(1808548329));

    System.out.println(solutionV2020.trailingZeroes2(3));
    System.out.println(solutionV2020.trailingZeroes2(5));
    System.out.println(solutionV2020.trailingZeroes2(11));
    System.out.println(solutionV2020.trailingZeroes2(25));
    System.out.println(solutionV2020.trailingZeroes2(1808548329));
}

GitHub代码

algorithms/leetcode/leetcode/_172_FactorialTrailingZeroes.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_172_FactorialTrailingZeroes.java


上一篇 LeetCode.355.Design Twitter 设计推特

下一篇 LeetCode.程序员面试金典.1603.Intersection 交点

阅读
评论
558
阅读预计3分钟
创建日期 2020-04-12
修改日期 2020-04-12
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论