LeetCode172-阶乘后的零

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/factorial-trailing-zeroes/

中文链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes/

题目详述

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

1
2
3
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

1
2
3
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零。

说明: 你算法的时间复杂度应为 O(log n) 。

题目详解

  • n! 尾数中零是由 2 乘以 5 得到的，所以我们需要知道 2 * 5 的对数，而 2 的个数是不少于 5 的个数的，所以我们只需要知道 n! 中因子 5 的个数。
  • 例如对于 100! ，从 1 到 100 中 5 的因子有 100 / 5 = 20 个，但是 25 = 5 * 5，每个 25 的因子还要额外贡献一个 5，100 / 25 = 4。所以最终结果为 20 + 4 = 24。
  • 依此类推，如若存在 125 的因子，还需要在原来的基础上多贡献一个 5。n 依次除以 5^1、5^2、5^3…… 得到所有因子 5 的个数。
  • 时间复杂度应为 O(log n) 。
1
2
3
4
5
6
7
8
9
10
11
public class LeetCode_00172 {

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