Java 中的阶乘末尾零

给定一个数字 n。我们的任务是找出 n 的阶乘值中存在的所有末尾零的总数。请参阅以下示例以获得更好的理解。

示例：1

输入

int n = 6

输出 1

解释：数字 6 的阶乘是 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720。数字 720 中的末尾零的数量是 1。

示例：2

输入

int n = 10

输出 2

解释：数字 10 的阶乘是 10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800。数字 3628800 中的末尾零的数量是 2。

例如：3

输入

int n = 20

输出 4

解释：数字 20 的阶乘是 20! = 20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 2432902008176640000。数字 2432902008176640000 中的末尾零的数量是 4。

朴素方法

在这种方法中，我们将计算 n! 的值，然后找出 n! 中末尾零的数量。其说明如下。

文件名： TrailingZeros.java

输出

The factorial of the number 5 is: 120
The number of trailing zeros in the number 120 is: 1

The factorial of the number 10 is: 3628800
The number of trailing zeros in the number 3628800 is: 2

The factorial of the number 20 is: 2432902008176640000
The number of trailing zeros in the number 2432902008176640000 is: 4

复杂度分析：由于程序使用 for 循环计算数字 n 的阶乘，因此程序的时间复杂度为 O(n)，其中 n 是输入数字。程序空间复杂度是常数，即 O(1)。

当 n! 的值变得非常大时，上述程序不适用。如果我们使用上述程序计算 50! 的值，我们会得到 -3258495067890909184。在这个数字中，末尾零的数量是 0，这是错误的。首先，任何数字的阶乘都不可能为负数。此外，50! 的值为 30414093201713378043612608166064768844377641568960512000000000000，该数字中的末尾零数量为 12，而上述程序在这两种情况下都会失败。因此，我们需要一种方法可以在不计算阶乘的情况下找到末尾零。以下方法解决了同一个问题。

另一种方法：不计算阶乘

让我们举一个例子来理解一个数字何时有末尾零。

假设我们取数字 3。我们看到 3 没有末尾零。现在将数字 3 乘以 10。我们得到 3 x 10 = 30，其中末尾零的数量是 1。请注意，10 也有一个末尾零。再次，将数字 3 乘以 100。我们得到 3 x 100 = 300，其中末尾零的数量是 2。请注意，100 也有 2 个末尾零。因此，我们看到一个数字中的末尾零数量取决于 10 的倍数。100 是 2 个十的倍数。10 x 10 = 100，因此有 2 个末尾零。1000 是三个十的倍数，10 x 10 x 10 = 1000，因此有 3 个末尾零。因此，我们所要做的就是找出给定数字 n 的阶乘中有多少个十。

现在问题来了，我们如何得到 10？10 只是 2 和 5 的乘积。因此，我们需要找出数字 *n* 的阶乘中有多少对 2 和 5，这最终归结为数字 *n* 的阶乘中存在的五的数量。这是因为数字 *n* 的阶乘中五的数量总是小于数字 *n* 的阶乘中二的数量。例如：从 1 到 8，只有一个 5 和多个二。

1 有零个二和零个五。(1 x 1 = 1)

2 有 1 个二和零个五。(2 x 1 = 2)

3 有零个二和零个五。(3 x 1 = 3)

4 有 2 个二和零个五。(2 x 2 = 4)

5 有零个二和 1 个五。(5 x 1 = 5)

6 有 1 个二和零个五。(2 x 3 = 6)。

7 有零个二和零个五。(7 x 1 = 7)

8 有 3 个二和零个五。(2 x 2 x 2 = 8)

因此，从 1 到 8，我们有 (1 + 2 + 1 + 3) 7 个二和一个五。因此，我们看到五的数量少于二的数量。因此，我们只得到一对，因为只有一个五。因此，8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40320 中的末尾零数量是 1，而数字 40320 只有一个末尾零。因此，我们的答案是正确的。现在，让我们看看实现。

文件名： TrailingZeros1.java

输出

The factorial of the number 5 has: 1 trailing zeros.

The factorial of the number 10 has: 2 trailing zeros.

The factorial of the number 50 has: 12 trailing zeros.

复杂度分析：该程序的时间和空间复杂度与前一个程序相同。由于上述程序不计算数字的阶乘，因此即使对于大数字，它也足以找到末尾零。

下面提到了编写上述程序的更好方法。以下程序比前一个程序更优化。

最优化方法

从前面的程序可以明显看出，如果我们计算输入数字中 5 的数量，我们就可以找到末尾零的数量。因此，我们所要做的就是应用循环并将数字除以 5 来减小它。其说明如下。

文件名： TrailingZeros2.java

输出

The factorial of the number 5 has: 1 trailing zeros.

The factorial of the number 10 has: 2 trailing zeros.

The factorial of the number 50 has: 12 trailing zeros.

复杂度分析：程序的 time complexity 为 O(log₅(n))，其中 n 是输入数字。我们之所以得到这个 time complexity，是因为我们将数字 *num* 除以 5 来减小它。程序的 space complexity 与前一个程序相同。