Simplify this python code

Question

I've written a program to check if my thought about solution on paper is right (and it is).

The task: how many zeros is in the back of multiplication of all numbers from 10 to 200.

It is 48 and it is a simple to calculate manually.

I never write on python seriously and this is what I get:

mul = 1
for i in range(10, 200 + 1):
    mul *= i

string = str(mul)
string = string[::-1]
count = 0;
for c in str(string):
    if c == '0':
        count += 1
    else:
        break

print count
print mul

I bet it is possible to write the same more elegant in such language like a python.

ps: yes, it is a homework, but not mine - i just helped a guy ;-)

irrelephant · Accepted Answer · 2010-10-27T00:11:57.487

11

A straight-forward implementation that doesn't involve calculating the factorial (so that it works with big numbers, ie 2000000!) (edited):

fives = 0
twos = 0
for i in range(10, 201):
   while i % 5 == 0:
      fives = fives + 1
      i /= 5
   while i % 2 == 0:
      twos = twos + 1
      i /= 2
print(min(fives, twos))

edited Oct 27 '10 at 00:11

answered Oct 26 '10 at 23:53

irrelephant

4,091
2
25
41

3

It counts the number of fives and twos in the prime factorization of the factorial iteratively (so 10! would have 2 fives and 8 twos). Since 5 * 2 = 10, and no other prime numbers can be multiplied to 10, the number of 10's in the factorization (which is the number of trailing zeroes) is the minimum of the number of fives and the number of twos in the prime factorization. The number of fives and twos is a lot smaller than the calculated factorial. – irrelephant Oct 27 '10 at 00:54
3

Although the question does call for 10-200, this is definitely a better approach for much larger numbers. For smaller numbers, actually doing the multiplication turns outs to be faster (at least when I ran timeit tests). – snapshoe Oct 27 '10 at 01:02
That's a really interesting method. I like it. – Brendan Long Oct 27 '10 at 01:43
Well, I check this one just because it is readable, and as well has good math background. – zerkms Oct 27 '10 at 22:32

score 6 · Answer 2 · answered Oct 26 '10 at 23:34

6

import math

answer = str(math.factorial(200) / math.factorial(9))
count = len(answer) - len(answer.rstrip('0'))

Import the math library
Calculate the factorial of 200 and take away the first 9 numbers
Strip away zeros from the right and find out the difference in lengths

answered Oct 26 '10 at 23:34

Brian McKenna

45,528
6
61
60

The most laconic at this moment – zerkms Oct 26 '10 at 23:35
Wouldn't `reduce(operator.mul, xrange(10, 200 + 1))` be more efficient than the factorials + division? – Brendan Long Oct 26 '10 at 23:38
@Brendan Long: all answers are appreciated, but I will check the most elegant one ;-P – zerkms Oct 26 '10 at 23:41
1

Definitely - but we're going for simplicity. I think this solution would one of the most simple if you don't have much experience in functional programming. – Brian McKenna Oct 26 '10 at 23:42

score 4 · Answer 3 · answered Oct 27 '10 at 13:44

4

print sum(1 + (not i%25) + (not i%125) for i in xrange(10,201,5))

answered Oct 27 '10 at 13:44

Robert William Hanks

361
1
3
10

score 3 · Answer 4 · answered Oct 26 '10 at 23:29

3

import itertools
mul = reduce(lambda x,y: x*y, range(10, 200+1))
zeros = itertools.takewhile(lambda s: s == "0", reversed(str(mul)))
print len(list(zeros))

The second line calculates the product, the third gets an iterator of all trailing zeros in that number, the last prints the number of that zeros.

answered Oct 26 '10 at 23:29

Kos

70,399
25
169
233

2

Could replace `lambda x,y: x*y` with `operator.mul` – Ismail Badawi Oct 26 '10 at 23:36
And `range` with `xrange` (although it would be minor in this case) – Brendan Long Oct 26 '10 at 23:39
@Brendan Long: since we always iterate from the begin to the end of the range - doesn't `xrange` an overhead at all? – zerkms Oct 26 '10 at 23:40
@zerms: The only difference is that `range` creates the whole list upfront (and stores it in memory) while `xrange` just returns iterates over numbers (all it has to store is the current one). The memory and speed difference in this case would both be negligible, but I thought I'd point it out since it's the "pythonic" way (default in Python 3). – Brendan Long Oct 26 '10 at 23:44
1

@Brendan Long: I know the difference, but I always thought that the `xrange` is the right decision only for loops where we not sure that we will iterate it to the end. – zerkms Oct 26 '10 at 23:48
@zerkms: http://wiki.python.org/moin/PythonSpeed/PerformanceTips#Usexrangeinsteadofrange From what I can tell, you should only use `range` if you can't use `xrange` (you need slices, you need to iterate more than once, or other things like that). See http://stackoverflow.com/questions/135041/should-you-always-favor-xrange-over-range – Brendan Long Oct 26 '10 at 23:54

score 3 · Answer 5 · answered Oct 26 '10 at 23:29

3

len(re.search('0*$', str(reduce(lambda x, y: x*y, range(10, 200 + 1),1))).group(0))

answered Oct 26 '10 at 23:29

Lachezar

6,523
3
33
34

1

but beautiful if you are into functional programming, eye of the beholder and all! – Oct 27 '10 at 00:15
3

I wouldn't say that this is very functional. You don't see a lot of regular expressions in functional programming. – Brian McKenna Oct 27 '10 at 00:17

score 2 · Answer 6 · edited Jun 20 '20 at 09:12

2

Do you mean zeroes? What is null otherwise?

Wouldn't some mathematics make it simpler?

How many 5s in 200 is len([x for x in range(5, 201, 5)]) = 40

How many 25s in 200 is len([x for x in range(25, 201, 5) if x%25 == 0]) = 8

How many 125s in 200 is len([x for x in range(120, 201, 5) if x%125 == 0]) = 1

Total 5s = 49

200! = 5^49 * 2 ^49 * (other numbers not divisible by 2 or 5)

So there are 49 zeroes

edited Jun 20 '20 at 09:12

Community

1
1

answered Oct 26 '10 at 23:36

pyfunc

65,343
15
148
136

To be clear - it is 48, not 49 ;-) And I solved it manually in the similar way. The current question is just a curiosity about how to write the "bruteforce" algorythm in python. – zerkms Oct 26 '10 at 23:38
@zerkms: I was guessing that you must have done that already. Silly me! – pyfunc Oct 26 '10 at 23:43

score 0 · Answer 7 · answered Oct 26 '10 at 23:36

0

mul = str(reduce(lambda x,y: x*y, xrange(10, 201)))
count = len(mul) - len(mul.rstrip("0"))

answered Oct 26 '10 at 23:36

kindall

178,883
35
278
309

Simplify this python code

7 Answers7