Problem 1: Multiples of 3 and 5

• 🔒 Problem
  • 🔐 Key Idea
• 🔑 Solution
  • 🧭 Initial idea
  • 🔨 Bruteforce method
  • 🔁 Function method (from overview)

🔒 Problem

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.

🔐 Key Idea

using mathematical concepts to reduce the iteration number

🔑 Solution

🧭 Initial idea

$O(1)$ complexity.

Using the mathematical concept of sum of multiples exists as a pair in a range.

For example, for the sum of multiples of 2 not exceeding 8, there would be 5 pairs with equal sum: (2, 8), (4, 6). These pairs sum to 2 + 8, which is the minimum and the maximum multiple. Numbers with odd number of multiples, we can just add (min + max) // 2 to the sum.

k = 999

f = [3, 5, 15]  # factors
n = [k//3, k//5, k//15]  # number of multiples
max = [k - k%3, k - k%5, k - k%15]  # biggest multiples for each factor 
sum = []  # sum of each factors

for i in range(3):
    minmax = f[i] + max[i]
    s = (n[i] // 2) * minmax

    if n[i] % 2 is 1:
        s += minmax // 2

    sum.append(s)

print(str(sum[0] + sum[1] - sum[2]))

233168

Warning: Since it’s defined in the problem as ’below 1000’, it shouldn’t contain 1000.

Tip: Consider the range with operands such as <, >, etc.

Note: Clarify the range of the problem before diving into it.

🔨 Bruteforce method

$O(n)$ complexity.

s = 0
for i in range(1000):
    if i % 3 is 0 or i % 5 is 0:
        s += i

print(s)

233168

🔁 Function method (from overview)

$O(1)$ complexity.

Tip: Use functons or external blocks for complicated for loops or loops with small iteration count.

k = 999

def get_multiple_sum(f):
    n = k // f
    max = k - k % f
    sum = (f + max) * (n // 2)

    if n % 2 is 1:
        sum += (f + max) // 2

    return sum

print(str(get_multiple_sum(3) + get_multiple_sum(5) - get_multiple_sum(15)))

233168