## Friday, February 3, 2017

### Count digits in a factorial - GeeksforGeeks

Count digits in a factorial | Set 1 - GeeksforGeeks
Given an integer n, find the number of digits that appear in its factorial, where factorial is defined as, factorial(n) = 1*2*3*4……..*n and factorial(0) = 1

A naive solution would be to calculate the n! first and then calculate the number of digits present in it. However as the value for n! can be very large, it would become cumbersome to store them in a variable (Unless you’re working in python!) .
A better solution would be to use the useful property of logarithms to calculate the required answer.
```We know,
log(a*b) = log(a) + log(b)

Therefore
log( n! ) = log(1*2*3....... * n)
= log(1) + log(2) + ........ +log(n)

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

Hence, output would be : floor(log(n!)) + 1.```
`int` `findDigits(``int` `n)`
`{`
`    ``// factorial exists only for n>=0`
`    ``if` `(n < 0)`
`        ``return` `0;`

`    ``// base case`
`    ``if` `(n <= 1)`
`        ``return` `1;`

`    ``// else iterate through n and calculate the`
`    ``// value`
`    ``double` `digits = 0;`
`    ``for` `(``int` `i=2; i<=n; i++)`
`        ``digits += ``log10``(i);`

`    ``return` `floor``(digits) + 1;`
`}`

http://www.geeksforgeeks.org/count-digits-factorial-set-2/
However that solution would not be able to handle cases where n >10^6
So, can we improve our solution ?
Yes ! we can.
We can use Kamenetsky’s formula to find our answer !
```It approximates the number of digits in a factorial by :
f(x) =    log10( ((n/e)^n) * sqrt(2*pi*n))

Thus , we can pretty easily use the property of logarithms to ,
f(x) = n* log10(( n/ e)) + log10(2*pi*n)/2

```
And that’s it !
Our solution can handle very large inputs that can be accommodated in a 32 bit integer,
`long` `long` `findDigits(``int` `n)`
`{`
`    ``// factorial of -ve number doesn't exists`
`    ``if` `(n < 0)`
`        ``return` `0;`

`    ``// base case`
`    ``if` `(n <= 1)`
`        ``return` `1;`

`    ``// Use Kamenetsky formula to calculate the`
`    ``// number of digits`
`    ``double` `x = ((n*``log10``(n/M_E)+``log10``(2*M_PI*n)/2.0));`

`    ``return` `floor``(x)+1;`
`}`