Breaking News

Friday, March 25, 2011

Find trailing zeros in a factorial number

How many zeros are at the end of "1000!" (one thousand factorial)?

No cheating... calculator is not allowed! Btw, you cant calculate that, because of the

I hope you are not thinking about multiplying all the numbers, are you?

N! = N x (N-1)!

The trick is around the the number Five(5).

STEP 1: Divide the number by 5, and note down the remainder
STEP 2: If the remainder is greater than 5, goto step 1
STEP 3: Add all remainders

Yep, thats it.

Lets have an example.

Example 1: 6!
=> 6/5 = 1 (This means, expect one (1) trailing zero at the end of 6!)

Example 2: 10!

10/5 = 2 (Expect two zeros)

Example 3: 50!

50/5 = 10
10/5 = 2
=> 10 + 2= 12 (Expect 12 trailing zeros)

Example 4: 100!

100/5 = 20
20/5 = 4
=> 20+4 (Expect 24 zeros)

I am leaving 1000! as an exercise for the reader (0:

Btw, no standard C data type can handle numbers this large. Unless you use some Mathlab library or your own code with some arbitrary data type restricted only to the available memory, you might be able to write a program. So, just find out the number of trailing zeros; and if you want to validate the answer using Calculator, try for 15!, 25!, 35!, etc...

Enjoy!

5 comments:

  1. Anonymous1:03 AM

    Thanks. This helped me to write a program!

    ReplyDelete
  2. Anonymous8:48 AM

    Hey this partially correct. You should also divide the number by 25,125,625,...

    ReplyDelete
  3. Anonymous2:15 PM

    Nice!
    I was sure there is a way without calculating the actual factorial :))

    ReplyDelete
  4. Anonymous5:32 PM

    Thanks Kamran, this is a good one, and very simple explanation!

    Another nice one:

    Algorithm to find number of trailing zeros factorial

    ReplyDelete
  5. Anonymous11:20 AM

    You are adding the quotients not the remainders. The remainder is always 0.

    ReplyDelete

Designed By Published.. Blogger Templates