> You really aren't doing much so there's not a lot to optimize that I can
> see. You could try asking on comp.lang.python, lots of people there are
> good at optimization.
** spoiler space: don't read ahead here unless you've attempted this
problem already, or if you don't want to be spoiled **
********************************************************************
You may be able to treat this as a combinatorial problem: how many ways
can you get a factor of 10 from the product of all those numbers? Every
factor of ten contributes to a trailing zero, so if we can count those,
we're done.
Concretely: if we're computing 10! factorial, imgaine we have the numbers
1-10 in front of us.
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
Next, we'll do something a little funny: we break up everything into its
prime factors:
1 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 3 * 3 * 3 * 3 * 5 * 5 * 7
Chop chop. Then we know that we're going to get a trailing zero when we
multiply with the first five:
2 * 5
and we also get a trailing zero when we multiply with the other five:
2 * 5
Even without computing the factorial, we know there's going to be two
trailing zeros in 10!, because there's only two ways of making tens.
The key is to see that factors of five can be combined with the
overabundance of twos that we have: that's how we can get tens. And those
tens are going to contribute to trailing zeros in the final product.
There are some complications, because some numbers produce more than one
factor of five (like 25, for example...), but they can be handled with a
little thought.
As a reference point: because you're explicitely given the upper bounds on
this assignment, this problem should be solvable in constant time, with a
single math formula.
Good luck.
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
