## Problem 1 - Multiples of 3 and 5

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.

### Iterative solution

#### it gets very slow for 1,000,000 because its time complexity is O(n) (linear)

def sum(maximum, multiplier): sum = 0 for x in range(multiplier, maximum, multiplier): sum += x return sum target = 1000 print sum(target, 3) + sum(target, 5) - sum(target, 3 * 5)

### Fastest solution

#### it never gets slow because its time complexity is O(1) (constant)

def sum(maximum, interval): maximum -= 1 an = maximum - (maximum % interval) n = int(maximum / interval) return n * (interval + an) / 2 target = 1000 print sum(target, 3) + sum(target, 5) - sum(target, 3 * 5)

## No comments:

Post a Comment