[Leetcode][172. 阶乘后的零] 3种方法：暴力大数，计算5的个数，对数时间复杂度

By Long Luo

Leetcode 172. 阶乘后的零 题解：

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

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

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 + logn)$，但 $logn$ 很快，只有 $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$ 的因子数有多少即可。

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 + ...$$

public static int trailingZeroes(int n) {
	int ans = 0;
	while (n > 0) {
		n /= 5;
		ans += n;
	}

	return ans;
}

复杂度分析

• 时间复杂度：$O(logn)$。

在这种方法中，我们将 $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. 😉😃💗