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.

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)

**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)

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

ReplyDeletewhere log is base 10.

there is a small bug ...

ReplyDeletenumber of digits = floor(log n + log n-1 + ... + log 2) + 1

u can reason it out why ....

This comment has been removed by the author.

ReplyDeleteokay I got it...fails for 1 :)

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

ReplyDeleteCheers...

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

ReplyDelete@sachin ...

ReplyDeleten! = 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

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

ReplyDelete@swapnil .. consider a case where n! = 10^x ... in that case

ReplyDeletelog(1) + log(2) ... log(n) = log(10^x) = x ..

but the correct answer is x+1

Regards

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

ReplyDeletealso n = 0 XD

ReplyDelete