Solving the "Digits in Factorial" Problem Using the First Law of Logarithms

logarithm-laws.java

Today, I tackled the algorithmic challenge of counting digits in a factorial, and I initially approached it using the naive method—calculating the factorial of a number and then counting the digits. However, I encountered a hurdle with overflow despite the O(n) time complexity.

Fortunately, I found a solution by applying a simple yet powerful formula known as the First Law of Logarithms. Here's the straightforward approach to solving the "Digits in a Factorial" problem:

We know that log(a*b) = log(a) + log(b). Therefore, we can express the logarithm of n! as the sum of individual logarithms:

log( n! ) = log(123……. * n) = log(1) + log(2) + …….. + log(n)

This approach efficiently addresses the challenge and avoids the issues associated with overflow.
  
 static int findDigits(int n){
        if (n < 0)
            return 0;
 
        if (n <= 1){
            return 1;
        }
        double digits = 0;
        for (int i = 2; i <= n; i++){
             digits += Math.log10(i);
        }
        return (int)(Math.floor(digits)) + 1;
    }