def sum_natural_numbers_till(n): return int((n * (n+1))/2) def find_multiples(n): # runs in O(1) instead of O(n) total = 0 if n <= 0: return 0 fours = n // 4 if n % 4 != 0 else n // 4 - 1 sixes = n // 6 if n % 6 != 0 else n // 6 - 1 twelves = n // 12 if n % 12 != 0 else n // 12 - 1 total = 4 * sum_natural_numbers_till(fours) + 6 * sum_natural_numbers_till(sixes) - 12 * sum_natural_numbers_till(twelves) return total
- def sum_natural_numbers_till(n):
- return int((n * (n+1))/2)
- def find_multiples(n):
- # runs in O(1) instead of O(n)
- total = 0
for i in range(0, n, 2):if i % 4 == 0 or i % 6 == 0:total += ireturn total- if n <= 0:
- return 0
- fours = n // 4 if n % 4 != 0 else n // 4 - 1
- sixes = n // 6 if n % 6 != 0 else n // 6 - 1
- twelves = n // 12 if n % 12 != 0 else n // 12 - 1
- total = 4 * sum_natural_numbers_till(fours) + 6 * sum_natural_numbers_till(sixes) - 12 * sum_natural_numbers_till(twelves)
- return total