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?

• FreezePhoenix: Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review.
• remedcu: The code in the question work for 4 out of 6 cases, and HackeRank does not reveal the test cases so I asked if there is any way to improve the performance of the above code.
• maxb: Try using the fact that \3ドル+6+9+...+3n = 3(1+2+3+...+n) = \frac{3n(n+1)}{2}\,ドル and see what you can do with that.
• Graipher: If your first code runs without a RuntimeError and just generates a time-out, that part would be on-topic (and you should add the tag time-limit-exceeded).
• Mast: I've removed the code that doesn't work.

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} = 1⁄2n(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).