On Tue, 25 Sep 2007, Ian Witham wrote:
> I am attempting to do this <https://www.spoj.pl/problems/FCTRL/> project for
> the Sphere Online Judge.
(Summary of the problem: for a given integer N, determine the number of
trailing zeroes in N! For example, for N=10, N! = 3628800, so the number
of trailing zeroes is 2.)
> for d in testnums:
> maxer = int(d ** .2) + 1
> g = sum(d / (5 ** x) for x in xrange(1, maxer))
> sys.stdout.write('%d\n' % g)
>
> ############
>
> Any ideas on how to speed this up?
I think you're on the right track, but it can actually be much less
computationally intensive.
The track I think you're on is that each trailing zero means that the
factorial, if factored out, had both a 2 and 5 among its factors (because
2x5 is 10, and the only way of getting 10). Furthermore, because there
are so many 2s, it's really about counting the number of times 5 is
multiplied in.
For example, in 10!, you have two occurances of 5: at 5 itself, and at 10
(2x5). For 30!, you'd have fives at 5, 10, 15, 20, 25, and 30, which at
first glance is 6; but since the 25 is actually 5x5, it counts for two,
for a total of 7. And, sure enough 20! is
265252859812191058636308480000000, with 7 trailing zeoes.
So, an approach might be:
1. Integer-divide N by 5. That gives the number of times it's divisible
by 5.
2. Integer-divide N by 5*5, i.e., 25; That gives the number of times it's
also divisible by 25.
3. Integer-divide N by 5*5*5, i.e, 125. That gives the number of times
it's also divided by 125
4. through whatever: keep doing this. You can stop when the result of the
integer division is zero.
If you add up all the counts you got in the previous steps, you now have a
number that tells you, if you were to have actually calculated N!, and
then factored it, the number of times 5 would have been a factor. And
since for each one of these there's at least one 2, you happen to also
have the count of how many times N! was multipled by 2*5, or 10, which is
also the number of trailing zeroes.
I just tried this approach out, using the values given at that web page,
and it works both quickly and accurately:
if __name__ == "__main__":
sampleinput = [3, 60, 100, 1024, 23456, 8735373]
sampleoutput = [0, 14, 24, 253, 5861, 2183837]
actualoutput = []
for n in sampleinput:
actualoutput.append(numfaczeroes(n))
assert actualoutput == sampleoutput
print actualoutput
C:\test\FCTRL>fctrl.py
[0, 14, 24, 253, 5861, 2183837]
I'll leave the coding of the numfaczeroes function as an exercise.
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
