project euler #1 using python time complexity


Problem #1 of Project Euler reads:

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 1000.

Here's my attempt:

T = int(input())

for i in range(T):
    sum = 0
    a = int(input())
    for j in range(a):
        if (j%3==0 or j%5==0):
            sum = sum + j

print(sum)

The code above raises an time complexity i.e., for some cases run for >10. you can find details here: enter image description here


Answer

You can calculate the sum of all natural numbers that are multiples of n and are below m as a trapezoidal area:

def sum_multiples(n, m):
    d = (m - 1) // n
    return (1 + d) * d // 2 * n

so that the sum of all the multiples of 3 or 5 below m can be calculated in a time complexity of O(1) by calculating the sum of all the multiples of 3 plus the sum of all the multiples of 5 minus the sum of all the multiples of 15, the lowest common denominator of 3 and 5:

def sum_3_5(m):
    return sum_multiples(3, m) + sum_multiples(5, m) - sum_multiples(15, m)

So to answer the question, sum_3_5(1000) returns:

233168