【Leetcode算法题】172. 阶乘后的零

By Long Luo

172. 阶乘后的零题目如下所示:

  1. 阶乘后的零

给定一个整数 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 <= 10^4

进阶:你可以设计并实现对数时间复杂度的算法来解决此问题吗?

方法一:计算1到n中全部5因子数量

思路与算法:

考虑到计算阶乘末尾的每个0表示乘以10,那么在我们在计算n!时乘以10的次数是多少?

考虑到两个数字a和b相乘,例如,要执行15 x 24 = 360,我们可以将其分解为:

15 x 24 = 3 x 5 x 2 x 2 x 2 x 3 = 360

从上面可以得出,我们只需要考虑2 x 5的因子有多少对。同时,因为2的因子数比5的因子数要多,所以我们只需要计算1到n的5的因子数有多少即可。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
public int trailingZeroes(int n) {
int ans = 0;
for (int i = 5; i <= n; i += 5) {
int temp = i;
while (temp % 5 == 0) {
ans++;
temp /= 5;
}
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(n)O(n)

为了计算零计数,我们循环从5到n的每五个数字处理一次,这里是O(n)步。

在每个步骤中,虽然看起来像是执行O(logn)O(logn)操作来计算5的因子数,但实际上它只消耗O(1)O(1),因为绝大部分的数字只包含一个因子5。可以证明,因子5的总数小于2n5\frac{2 \cdot n}{5}

所以我们得到O(n) x O(1) = O(n)。

  • 空间复杂度:O(1)O(1),只是用了一个整数变量。

方法二:

方法一还可以进一步改进,因为我们实际上只对5的因子感兴趣,而方法二需要每个5的倍数进行计算。那么,如何解决有多重因子的数字呢?

所有包含两个及以上的因子5的数字都是25的倍数。所以我们可以简单的除以25来计算25的倍数是多少。

我们每次将n本身除以5,这样可以得到一个系列:

n / 5 + n / 25 + n / 125 + …

代码如下所示:

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

return ans;
}

复杂度分析:

  • 时间复杂度:O(logn)O(\log n)
    在这种方法中,我们将nn除以55的每个幂。根据定义,55log5n\log_5n幂小于或等于nn。由于乘法和除法在32位整数范围内,我们将这些计算视为O(1)O(1)。因此,我们正在执行log5nO1=logn\log_5 n\cdot O(1)=\log n操作
  • 空间复杂度:O(1)O(1),只是用了常数空间。