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
. 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
#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:
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.
Top comments (0)