Project Euler Problem 1 with Python 3 ideal solution

Question

I have been playing around in hacker rank with Python these days, and now pulling my hair out on this question to solve the Euler's problem in the least time required.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below N.

Without that in mind, I initially wrote the below code:

t = int(input())
for a in range(t):
    n = int(input())
    temp=0
    for i in range(n):
        if(i%3==0 or i%5==0):
            temp+=i
    print(temp)

The above solves most of the test cases except #2 and #3 in HackerRank. On checking the discussion tab, I found out that we have to reduce the time required to avoid timeout as the #2 and #3 test cases inputs big numbers.

Can anyone help me to optimize my code further?

Answer 1

temp isn't a great name for your accumulator. Call it something like total, which gives a much clearer indication of what role it plays.

First, let's separate the logic from the I/O, to make it easier to test:

def sum_3s_and_5s(n):
    total = 0
    for i in range(n):
        if (i%3==0 or i%5==0):
            total+=i
    return total

if __name__ == "__main__":
    print(sum_3s_and_5s(10))

We can now focus on the implementation of sum_3s_and_5s. We can write the same algorithm more succinctly:

def sum_3s_and_5s(n):
    return sum([i * (i%3==0 or i%5==0) for i in range(n)])

This doesn't change the time complexity, of course - it still scales as O(n). What we need to do is think about the mathematics. What we're looking for is the sum of all the multiples of 3 in the range, added to all the multiples of 5, less the multiples of 15 (which are otherwise double-counted). Let's write a function to count multiples of k in a given range:

def sum_multiples(n, k):
    return sum([i * (i%k==0) for i in range(n)])

def sum_3s_and_5s(n):
    return sum_multiples(n,3) + sum_multiples(n,5) - sum_multiples(n, 15)

You might not think that's an improvement - and you'd be right, because we're now reading the whole range three times instead of once. But we can work or sum_multiples, to make it O(1). Remember the formula for triangular numbers: sum(i){0,n} = ½n(n+1). The sum of all the multiples of k is just k times the sum of integers from 0 to n/k. That gives us:

def sum_multiples(n, k):
    # subtract 1 from n, as range is exclusive
    n = (n-1) // k
    return k * n * (n + 1) // 2

Now it doesn't matter how big n gets, the calculation is constant time (or perhaps O(log n) if we get into big integers).