5

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 ;-)

Improve this question

7 Answers 7

Reset to default
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))
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

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.
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).
That's a really interesting method. I like it.
Well, I check this one just because it is readable, and as well has good math background.
6 
import math

answer = str(math.factorial(200) / math.factorial(9))
count = len(answer) - len(answer.rstrip('0'))
  1. Import the math library
  2. Calculate the factorial of 200 and take away the first 9 numbers
  3. Strip away zeros from the right and find out the difference in lengths
Improve this answer

4 Comments

The most laconic at this moment
Wouldn't reduce(operator.mul, xrange(10, 200 + 1)) be more efficient than the factorials + division?
@Brendan Long: all answers are appreciated, but I will check the most elegant one ;-P
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.
4 
print sum(1 + (not i%25) + (not i%125) for i in xrange(10,201,5))
Improve this answer

Comments

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.

Improve this answer

6 Comments

Could replace lambda x,y: x*y with operator.mul
And range with xrange (although it would be minor in this case)
@Brendan Long: since we always iterate from the begin to the end of the range - doesn't xrange an overhead at all?
@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: 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.
|
3 
len(re.search('0*$', str(reduce(lambda x, y: x*y, range(10, 200 + 1),1))).group(0))
Improve this answer

2 Comments

but beautiful if you are into functional programming, eye of the beholder and all!
I wouldn't say that this is very functional. You don't see a lot of regular expressions in functional programming.
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

Improve this answer

2 Comments

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: I was guessing that you must have done that already. Silly me!
0 
mul = str(reduce(lambda x,y: x*y, xrange(10, 201)))
count = len(mul) - len(mul.rstrip("0"))
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.