# Thread: interesting question, number of 0s at the end of N!

1. ## interesting question, number of 0s at the end of N!

Hello everyone,

My friend and I are discussing about an interesting question, how to calculate efficiently how many 0s are at the end of N! (1 * 2 * 3 * ... * N-1 * N).

Our algorithm is like this,

1. Use a loop to calculate N!
2. Use a loop to calculate %10 result of N!, then /10 each step

Are there any better solutions?

regards,
George

2. As I posted in another messageboard, I think the solution is to to calculate the integer division of N by 5. This should be the number of trailing zeros in N!

Oh, and even in your current algorithm you miss out the point that N! can be calculated directly from N without using a loop.

My reasoning is that we get a trailing zero every time there is an implicit (2 * 5). Every time we hit an even N, we implicitly multiply by 2 yet another time, but without a corresponding multiplication by 5, there is no trailing zero appended.

I am not a professional mathematician, and this is rather informal reasoning, so perhaps the mathematicians around here can provide a better solution or show that my reasoning is actually flawed.

EDIT:
Settled in that other messageboard with this link[.

3. For positive n/5 (in integer arithmetic) will give a lower bound for the number of trailing zeros at the end of n!

For n < 25 it is an exact lower bound. I'll leave as a challenge the analysis for n >= 25. An extra zero creeps in at n = 25 (as n is 5*5) and every multiple thereof. Similar effect occurs for n a multiple of 125 (5*5*5), 625 (5*5*5*5), .....

4. check this site out http://www.newdream.net/~sage/old/numbers/fact.htm - "Behold! The first 999 factorials"

you should see why we integer divide by 5 to get number of trailing zeros of n!.