### Using Kamenetsky's formula to count digits in a factorial

We need to count the number of digits in $$N!$$. We can do that by first calculating the $$N!$$, and then counting the number of digits. As we know the value of $$N!$$ can be very large so it would cause an overflow if we even try to store it in a unsigned long long variable.

So what to do now? We can use the property of logarithms.

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$$

Here is the code for it:

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}$$

Here is the code:

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

Voila! We're done. It's now time for some quote reading:

“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

1. Surprisingly amazing.

2. I agree. The algorithm just stunned me.

3. Damn boi... way to go!

4. Thank you so much!