### Problem statement:

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. In the case of HackerRank, we have to find the sum of multiples below N.

*Links: Project Euler, HackerRank*

### #1 Naive Solution:

The straightforward solution will be to iterate through all numbers and add numbers that are divisible by 3 or 5. Please refer to the below code. The code here will take
$O(n)$
. This seems okay for the Project Euler constraint where
$N$
is
$1000$
. However, this code will result in a TLE for the HackerRank problem where
$N$
can be up to
$10^9$
.

```
def slow_sum_of_multiples_of_3_or_5(till: int) -> int:
sum_of_multiples = 0
for num in range(till):
if num % 3 == 0 or num % 5 == 0:
sum_of_multiples += num
return sum_of_multiples
```

### #2 Pythonic Naive Solution:

We can make the above solution more compact using python's list comprehension. This will not make the code faster.

```
def pythonic_sum_of_multiples_of_3_or_5(till: int) -> int:
return sum(x for x in range(till) if x % 3 == 0 or x % 5 == 0)
```

### #3 Using Arithmetic Progression:

Multiples can be considered as Arithmetic Progression where the common difference is the divisor.

We have direct formula to calculate addition of arithmetic progression:

The code for this will look something like this:

```
def sum_of_arithmetic_progression(first: int, last: int, no_of_elements: int) -> int:
return (first + last) * no_of_elements // 2
```

Now we need to add the sum of all multiples of 3 and all multiples of 5.

*Multiples of 3:*
$3, 6, 9, 12, \mathbf{15}, 18, 21, 24, 27, \mathbf{30}, ...$

*Multiples of 5:*
$5, 10, \mathbf{15}, 20, 25, \mathbf{30}, 35, 40, ...$

As you can see above, if we do add the multiples, we will be getting additional multiples of 15. Because some numbers are divisible by both 3 and 5 and we will be adding them twice. So to get the correct addition we need to subtract multiples of 15 (LCM of 3 and 5 i.e. numbers that are divisible by both 3 and 5) from the addition of multiples of 3 and multiples of 5. The formula will look something like this:

Please see the complete code below. This code will take consistent time for any given
$N$
. So, the time complexity for this will be
$O(1)$
.

```
def fast_sum_of_multiples_of_3_or_5(till: int) -> int:
till -= 1 # We don't want to include `till` in our summation.
def sum_of_multiples(of: int) -> int:
""" Short hand function to return sum of arithmetic progression. """
no_of_elements_divisible = till // of
last_divisible = no_of_elements_divisible * of
return sum_of_arithmetic_progression(
first=of, last=last_divisible, no_of_elements=no_of_elements_divisible)
return sum_of_multiples(of=3) + sum_of_multiples(of=5) - sum_of_multiples(of=15)
def sum_of_arithmetic_progression(first: int, last: int, no_of_elements: int) -> int:
return (first + last) * no_of_elements // 2
```

Thank you for reading.

## Top comments (0)