January 16, 2009

Finding First Non-Zero Digit of N Factorial

Find the first non-zero digit of N!. Assume N! to be extremely large.

Solution:
If we assume that the product doesnt contain either of 2's and 5's, then finding last digit is trivial. Simple multiply the result with next number and take its mod 10. The problem is complicated as 2's and 5's lead to trailing 0's. So the first step is to remove 2's and 5's. Then solve the problem. The cancel 5's with 2's and multiply back the left over 2's.

For Ex. 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7. We extract 2's and 5's so the product is 1 * 3 * 3 * 7. The trailing digit is 3. We have extracted four 2's and one 5. So we get 3 extra 2's. So multiply to 3 we get 4 as the answer. To check 7! = 5040
d = 1 
n2 = 1
for i = 3 to n
  j = i

  while j%10 == 0 //remove trailing zeros
    j /= 10

  while j%2 == 0 //count of 2's
    j /= 2
    n2 += 1

  while j%5 == 0 //cancel a 5 with a 2
    j /= 5
    n2 -= 1    

  d = (d * j) % 10

d = (d * 2^n2) % 10 //multiply remaining 2's to d
return d

3 comments:

  1. Good one - thanks! Another nice page that is similar:

    Find trailing zeros in Java

    ReplyDelete
  2. Each 10 numbers will multiply to a trailing 8. Which creates a repeating cycle every 40 numbers.

    f x = ((x/10)^8) * f (x mod 10)

    8 power n cycle is: 8 6 4 2 8 .....

    f (x+10) = f ((x mod 40) + 10)


    ReplyDelete