[Tutor] Can my code be optimized any further (speed-wise)?

[Danny Yoo]

> 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.