跳转至

面试题 16.05. 阶乘尾数

题目描述

设计一个算法，算出 n 阶乘有多少个尾随零。

示例 1:

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

示例 2:

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

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

解法

方法一：数学

思考

\(n!\) 末尾零来自因子 \(10=2\times 5\)，而 \(2\) 远比 \(5\) 多，故零的个数等于 \([1,n]\) 中 \(5\) 的个数（含 \(25\)、\(125\) 等更高次）。

直接算阶乘再数零在 \(n\) 稍大时溢出。

反复 \(n//=5\) 并累加，分别计入 \(5\)、\(5^2\)、\(5^3\ldots\) 的贡献，时间 \(O(\log n)\)。

题目实际上是求 \([1,n]\) 中有多少个 \(5\) 的因数。

我们以 \(130\) 为例来分析：

  1. 第 \(1\) 次除以 \(5\)，得到 \(26\)，表示存在 \(26\) 个包含因数 \(5\) 的数；
  2. 第 \(2\) 次除以 \(5\)，得到 \(5\)，表示存在 \(5\) 个包含因数 \(5^2\) 的数；
  3. 第 \(3\) 次除以 \(5\)，得到 \(1\)，表示存在 \(1\) 个包含因数 \(5^3\) 的数；
  4. 累加得到从 \([1,n]\) 中所有 \(5\) 的因数的个数。

时间复杂度 \(O(\log n)\)，空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        while n:
            n //= 5
            ans += n
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        while (n > 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while (n) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func trailingZeroes(n int) int {
    ans := 0
    for n > 0 {
        n /= 5
        ans += n
    }
    return ans
}

1
2
3
4
5
6
7
8
function trailingZeroes(n: number): number {
    let ans = 0;
    while (n) {
        n = Math.floor(n / 5);
        ans += n;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    func trailingZeroes(_ n: Int) -> Int {
        var count = 0
        var number = n
        while number > 0 {
            number /= 5
            count += number
        }
        return count
    }
}

评论