# 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 Author
Mayukh Datta