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.
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
. This seems okay for the Project Euler constraint where
. However, this code will result in a TLE for the HackerRank problem where
can be up to
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
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)
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:
Multiples of 5:
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
. So, the time complexity for this will be
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.