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
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[.
Last edited by laserlight; 06-03-2006 at 02:16 AM.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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), .....
Last edited by grumpy; 06-03-2006 at 03:15 AM.
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!.
