## Friday, January 21, 2011

### Number of digits

Given a positive number n find the number of digits in factorial n. 'n' can be very large (may be 10^4) so consider the case of the overflow.

Approach:
Lets analyse how we can find the number of digits in any give number
If the given number is x = 10^y (x being an integer and y being a float)
The number of digits = floor(y) + 1
So y = log10(x)

Now to find the number of digits in n!, we need to find the
y = log(n!) = log(1*2*3*4.......*n) = log(1) + log(2) + log(3) + ......+ log(n)

1. number of digits = ceil(log n + log n-1 + ... + log 2)

where log is base 10.

2. there is a small bug ...
number of digits = floor(log n + log n-1 + ... + log 2) + 1
u can reason it out why ....

3. This comment has been removed by the author.

4. okay I got it...fails for 1 :)

5. actually it fails for any number of the form 10^n .. u figured out for n=0 :) ...
Cheers...

6. can you please explain how did you get to this equation??

7. @sachin ...
n! = 1*2*3*4....*n
log(n!) = log(1) + log(2) .... + log(n)
now log(n!) gives x which is 10^x = n!
Clearly x is the number of digits ... Rest corner cases u can work it out ... Cheers

8. @aviral: if you are taking number of format 10^n (n>1) as input, then also it won't fail...as I think so... :)

9. @swapnil .. consider a case where n! = 10^x ... in that case
log(1) + log(2) ... log(n) = log(10^x) = x ..
but the correct answer is x+1
Regards

10. The only case where n! = 10^x for integers n and x is n=1.

11. also n = 0 XD