Utilitize the basic properties of multiples and sums.
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.
# Target number used to limit iteration
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.
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
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