By Long Luo

Leetcode 172. 阶乘后的零 题解：

方法一：用大数暴力求解并计算末尾0的数量

因为 \(n!\) 得到的数字会非常大，所以需要使用BigInteger，得到结果之后，再计算末尾 \(0\) 的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import java.math.BigInteger;

class Solution {
    public int trailingZeroes(int n) {
        BigInteger nFactorResult = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            nFactorResult = nFactorResult.multiply(BigInteger.valueOf(i));
        }

        int ans = 0;
        while (nFactorResult.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
            ans++;
            nFactorResult = nFactorResult.divide(BigInteger.TEN);
        }

        return ans;        
    }
}

复杂度分析

• 时间复杂度：\(O(n)\), 实际上应该是 \(O(n + \log n)\)，但 \(\log n\) 很快，只有 \(O(1)\)，所以 \(O(n)\) 。
• 空间复杂度：\(O(1)\)。

方法二：计算1到n中全部5因子数量

思路与算法：

考虑到计算阶乘末尾的每个 \(0\) 表示乘以 \(10\)，那么在我们在计算 \(n!\) 时乘以 \(10\) 的次数是多少？ 考虑到两个数字 \(a\) 和 \(b\) 相乘，例如，要执行 \(15 \times 24 = 360\)，我们可以将其分解为：

\[ 15 \times 24 = 3 \times 5 \times 2 \times 2 \times 2 \times 3 = 360 \]

从上面可以得出，我们只需要考虑 \(2 \times 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)\)。

为了计算零计数，我们循环从 \(5\) 到 \(n\) 的每五个数字处理一次，这里是 \(O(n)\) 步。 在每个步骤中，虽然看起来像是执行 \(O(logn)\) 操作来计算 \(5\) 的因子数，但实际上它只消耗 \(O(1)\)，因为绝大部分的数字只包含一个因子 \(5\)。可以证明，因子 \(5\) 的总数小于 \(\frac{2 \cdot n}{5}\)。 所以我们得到 \(O(n) \times O(1) = O(n)\)。

• 空间复杂度：\(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(\log n)\)。

在这种方法中，我们将 \(n\) 除以 \(5\) 的每个幂。根据定义，\(5\) 的 \(\log_5n\) 幂小于或等于 \(n\)。由于乘法和除法在32位整数范围内，我们将这些计算视为 \(O(1)\)。因此，我们正在执行 \(\log_5 n \cdot O(1) = \log n\)操作。

• 空间复杂度：\(O(1)\)，只是用了常数空间。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗