Digit Count in a Factorial Of a Number in Java

A number n is given to us. Our task is to find the total count of digits present in the number n!.

Example 1:

Input

int n = 9

Output: 6

Explanation: The value of 9! is 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362880. The total number of digits present in the number 362880 is 6. Hence, the outcome is 6.

Example 2:

int n = 12

Output: 479001600

Explanation: The value of 12! is 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 479001600. The total number of digits present in the number 479001600 is 9. Hence, the outcome is 9.

Naïve Approach:

In the naïve approach, we will first compute the factorial of the given number, and after that, we will find the number of digits present in the factorial of the given number. The illustration of the same is mentioned in the following program.

FileName: CntFactDig.java

Output:

The factorial of the number 9 has 6 digits.

The factorial of the number 12 has 9 digits.

Complexity Analysis: The program uses a for loop and a while loop. The for loop takes O(N) time, and the while loop takes O(log(N)) time. Therefore, the time complexity of the program is O(N + log(N)), where N is the number whose factorial is to be found.

The above approach works well. However, for the larger inputs, it is not possible for the above approach to work properly. For n = 50, 50! = 50 x 49 x 48 x 47 x 46 x … x 45 x 44 … x 3 x 2 x 1 = 30414093201713378043612608166064768844377641568960512000000000000 and storing such a huge number in an int variable is not possible. One may argue that instead of int use long. However, long also has a limit, and that limit can also be exceeded when the factorial of a large number is computed. Thus, we see that no matter what kind of data type we use, the limit of the data type can easily be exceeded when the factorial of a large number is computed. Therefore, it is evident that computing the factorial of the number (in order to compute its digits) is not a foolproof approach. Hence, we need to find a way where computing the factorial of the number is not required.

Approach: Using Properties Of Logarithm

We know that,

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

Thus, log(q!) = log(1 x 2 x 3 x 4 x … q) = log(1) + log(2) + log(3) + log(4) + … + log(q)

Now, we see that (log₁₀ of number k) + 1 is the total number of digits present in the number k. We will use this concept to find the total number of digits present in n! in the following program.

FileName: CntFactDig1.java

Output:

The factorial of the number 9 has 6 digits.

The factorial of the number 12 has 9 digits.

Complexity Analysis: The program uses only one loop. Thus, the time complexity of the program is O(n), where n is the number whose factorial is to be found. The space complexity of the program is constant, i.e., O(1).

Approach: Kamenetsky's Formula

The straight forward approach is to use the Kamenetsky's formula for computing the number of digits present in the factorial of a number. The formula is:

P(n) = log₁₀(((n / e) ^ n) * sqrt(2 * Pi * n)), where e = 2.71828182845904523536, and

Pi = 3.141592654, and n is the number that will be given to the formula. One of the great advantages of using this formula is that this formula works well for large factorial values.

FileName: CntFactDig2.java

Output:

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.

Complexity Analysis: The time complexity of the program is constant. The space complexity of the program is also constant.

Note: We have assumed that Math.log₁₀( ) takes O(1) time.