Count Digits in a Factorial Using Logarithm in Java
Given an integer N, our task is to determine the total number of digits in the integer n!
Example 1:
Input:
int num = 5
Output:
The total number of digits of a factorial of a number is 3
Explanation:
If we calculate the factorial of the num = 5, then we get (5! = 5 * 4 * 3 * 2 * 1 = 120), and the factorial of the number is 120. In the result, the total number of digits is 3. Hence, it returns the output as 3.
Example 2:
Input:
int num = 9
Output:
The total number of digits of a factorial of a number is 6
Explanation:
If we calculate the factorial of the num = 9, then we get (9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362880), and the factorial of the number is 362880. In the result, the last two digits are 20. Hence, it returns the output as 6.
Approach: Using the properties of Logarithms
As we know that
log(x*y) = log(x) + log(y)
Hence
log(n! ) = log(1 * 2 * 3 ....... * n) = log(1) + log(2) + log(3)....... +log(n)
Now consider that each number's digit count is determined by multiplying the floor value of the log base 10 by 1, which holds for all numbers.
Implementation:
FileName: CountDigitsFactorial.java
import java.io.*;
import java.util.*;
public class CountDigitsFactorial
{
static int CountDigit(int num)
{
if (num < 0)
{
return 0;
}
if (num <= 1)
{
return 1;
}
double count = 0;
for (int i = 2; i <= num; i++)
{
count += Math.log10(i);
}
return (int)(Math.floor(count)) + 1;
}
public static void main(String[] args)
{
int num=5;
System.out.println("The total number of digits of a factorial of a number is " + CountDigit(num));
}
}
Output:
The total number of digits of a factorial of a number is 3
Complexity Analysis:
The above program has an O(N log N) time complexity due to the log calculations being done in a loop and an O(1) space complexity due to constant variables.
Approach: Using Stirling's approximation formula
For large values of num, this formula provides an accurate approximation of the real value of the factorial, where e represents the mathematical constant, and PI represents the mathematical constant pi. The modified Stirling's approximation formula implemented in this code determines the number of digits in the factorial using the logarithm of the original expression.
Implementation:
Filename: CountDigitsFactorial1.java
import java.io.*;
import java. lang.*;
import java. util.*;
public class CountDigitsFactorial1
{
static int CountDigit(int num)
{
if (num < 0)
{
return 0;
}
if (num <= 1)
{
return 1;
}
// calculating the digit's value
double t = (num * Math.log10( num / Math.E) + Math.log10(2 * Math.PI * num) / 2.0);
return (int) Math.floor(t) + 1;
}
public static void main(String[] args)
{
int num=9;
System.out.println("The total number of digits of a factorial of a number is " + CountDigit(num));
}
}
Output:
The total number of digits of a factorial of a number is 6
Complexity Analysis:
The abovementioned approach of using Stirling's approximation and logarithms to count the digits in n! has time complexity O(1), which denotes constant time complexity. At the same time, the space complexity is given by O(1), which is also constant.