Tuesday, February 16, 2016

Solving Project Euler Problem #1

A procedural solution

Drew Davis presents  a very nice solution to this problem at his blog
http://rdrewd.blogspot.com/2016/02/project-euler-problem-1-in-python.html?m=1

The final code he ends up with is

sum=0
for num in range(1000):
    if (num % 3)==0 or (num % 5) == 0:
        sum += num
print(sum)



There's nothing wrong with this solution, but it's very procedural and it requires examining every number from 1 to 1000.

A set based solution

There's another way to approach this.  We're being asked to sum the multiples of 3 and 5. Python's range function can give us those numbers directly without looping and without using the % operator.

multiples_of_3 = range(3, 1000, 3)
multiples_of_5 = range(5, 1000, 5)

There will be some duplication because any number that is a multiple of both 3 and 5 (like 15) will appear in both lists. The fix for this is to convert each list to a set and combine the sets with the "union" operator. This will eliminate any duplicates.

multiples = set(multiples_of_3) | set(multiples_of_5)

Now the only thing left is to print the sum.

print sum(multiples)

What about speed?

Here are both implementations and the timing results. The set based approach is about 3X faster.



def euler1a():
    multiples_of_3 = range(3,1000,3)
    multiples_of_5 = range(5,1000,5)
    multiples = set(multiples_of_3) | set(multiples_of_5)
    return sum(multiples)


def euler1b():
    sum=0
    for num in range(1000):
        if (num % 3)==0 or (num % 5) == 0:
            sum += num
    return sum




timeit euler1a()
10000 loops, best of 3: 30.4 µs per loop
timeit euler1b()
10000 loops, best of 3: 108 µs per loop


No comments:

Post a Comment