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)

11 comments :

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

    where log is base 10.

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

    ReplyDelete
  3. This comment has been removed by the author.

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

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

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

    ReplyDelete
  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

    ReplyDelete
  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... :)

    ReplyDelete
  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

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

    ReplyDelete