Skip to main content
  1. Articles/

Using Kamenetsky's formula to count digits in a factorial

·2 mins
Mayukh Datta
Problem Solving

We have to count the number of digits in \(N!\). We first calculate the \(N!\) and then count the number of digits. But when the value of \(N!\) is very large, it can cause an overflow even if we store it in a unsigned long long variable.

We can use the property of logarithms to circumvent the problem.

We know that,

\(log(ab) = log(a)+log(b)\)
\(\therefore log(n!) = log(1*2*3…* n)\)
\(= log(1)+log(2)+…+log(n)\)

The floor value of log base 10 increased by 1, of any number, gives the number of digits present in that number.

Hence, \(floor(log_{10}(n!)) + 1\)

C++ code:

int digitsInFactorial(int N)
{
    double digits = 0;
    if(N<=1){ return N; }
    for(int i=2;i<=N;i++){
        digits += log10(i);
    }
    return floor(digits) + 1;
}

The time complexity of the above code is \(O(n)\). We can further optimize it using Kamenetsky’s formula. Using this formula, we can count digits in a factorial for extremely large values of N.

It approximates the number of digits in a factorial by :

\(f(n) = \log_{10}( (n/e)^{n} \sqrt{2 \pi n})\)

After applying the property of logarithms we get,

\(f(n) = n log_{10}(n/e)+\dfrac{log_{10}(2 \pi n)}{2}\)

C++ code:

// Since the result can be large 
// long long is used for the return type
long long countdigits(int n){
    if(n <= 1)
        return n;
    else{
        double x = ((n * log10(n / M_E)) + (log10(2 * M_PI * n) / 2.0)); 
        return floor(x) + 1;
    }
}

The time complexity of the above code is \(O(1)\).

Voila! We’re done.

Now it’s time for some good quotes:

The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.

Donald E. Knuth, Selected Papers on Computer Science