Java 中数字阶乘的数字计数

给定一个数字 n。我们的任务是找到数字 n! 中存在的数字的总位数。

示例 1

输入

int n = 9

输出 6

解释: 9! 的值为 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362880。数字 362880 中存在的数字总数为 6。因此，结果是 6。

示例 2

int n = 12

输出 479001600

解释: 12! 的值为 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 479001600。数字 479001600 中存在的数字总数为 9。因此，结果是 9。

朴素方法

在朴素方法中，我们将首先计算给定数字的阶乘，然后查找给定数字的阶乘中存在的数字数量。相同内容的说明在下面的程序中给出。

文件名: CntFactDig.java

输出

The factorial of the number 9 has 6 digits.

The factorial of the number 12 has 9 digits.

复杂度分析: 该程序使用了一个 for 循环和一个 while 循环。for 循环需要 O(N) 时间，而 while 循环需要 O(log(N)) 时间。因此，程序的时间复杂度是 O(N + log(N))，其中 N 是要找到其阶乘的数字。

上述方法工作良好。然而，对于较大的输入，上述方法无法正常工作。对于 n = 50，50! = 50 x 49 x 48 x 47 x 46 x … x 45 x 44 … x 3 x 2 x 1 = 30414093201713378043612608166064768844377641568960512000000000000，将如此巨大的数字存储在 int 变量中是不可能的。有人可能会争辩说，与其使用 int，不如使用 long。但是，long 也有一个限制，当计算大数的阶乘时，也可以超出这个限制。因此，我们看到，无论使用哪种数据类型，在计算大数的阶乘时，数据类型的限制都可以轻松地被超过。因此，很明显，计算数字的阶乘（以便计算其位数）不是一种万无一失的方法。因此，我们需要找到一种不需要计算数字阶乘的方法。

方法：使用对数性质

我们知道：

log(p * q) = log(p) + log(q)

因此，log(q!) = log(1 x 2 x 3 x 4 x … q) = log(1) + log(2) + log(3) + log(4) + … + log(q)

现在，我们看到（数字 k 的 log₁₀）+ 1 是数字 k 中存在的数字总数。我们将使用这个概念在下面的程序中找到 n! 中存在的数字总数。

文件名: CntFactDig1.java

输出

The factorial of the number 9 has 6 digits.

The factorial of the number 12 has 9 digits.

复杂度分析: 该程序只使用一个循环。因此，程序的时间复杂度是 O(n)，其中 n 是要找到其阶乘的数字。程序空间复杂度为常数，即 O(1)。

方法：Kamenetsky 公式

直接的方法是使用 Kamenetsky 公式来计算数字阶乘中存在的数字数量。该公式是

P(n) = log₁₀(((n / e) ^ n) * sqrt(2 * Pi * n))，其中 e = 2.71828182845904523536，并且

Pi = 3.141592654，n 是将输入到公式中的数字。使用此公式的一个巨大优点是，该公式对于大阶乘值非常有效。

文件名: CntFactDig2.java

输出

The factorial of the number 9 has 6 digits.

The factorial of the number 12 has 9 digits.

The factorial of the number 50 has 65 digits.

复杂度分析: 程序的 time complexity 是常数。程序 space complexity 也是常数。

注意：我们假设 Math.log₁₀( ) 的时间复杂度为 O(1)。