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

---