I recently started a new blog series where I solve Project Euler problems and write about how I did it. This post addresses Problem 1.
So far, I’m sticking with the plan. Go me.
The GitHub repo is available here.
Anyway, let’s dive in.
The first problem states:
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.
The problem provides an example to start with. It shows how to find every number below 10 that’s a multiple of 3 or 5. Those are 3, 5, 6, and 9. Their sum is 23.
To solve the actual problem, we need to find every number below 1000 that is a multiple of 3 or 5. We can do 0 - 10 on paper (or in our heads). But calculating these numbers between 0 - 1000 is a little more time-consuming.
Luckily, we can solve this with a bit of programming.
My first solution
Here was my first solution.
func sumOfMultiples3And5(max: Int) -> Int {
var sum: Int = 0
for count in 1..<max {
guard count % 3 == 0 || count % 5 == 0 else { continue }
sum += count
}
return sum
}
This is a brute-force solution. It loops through every number from 1 to max, and if a number is divisible by 3 or 5, it adds it to a running sum.
My second solution
I then slightly rewrote the function. It’s still a brute-force approach. But it’s a little more concise.
func sumOfMultiples3And5(max: Int) -> Int {
(1..<max)
.filter { $0 % 3 == 0 || $0 % 5 == 0 }
.reduce(0, +)
}
This approach does the same thing but in a more concise way.
It builds a range from 1 to max, filters out numbers that aren’t divisible by 3 or 5, and then adds the rest using reduce.
This approach is very concise but not as readable as my first approach.
My third solution
While I was writing this blog post, I discovered another approach. This is a purely mathematical approach.
This approach uses an Arithmetic Progression. Honestly, I won’t do a great job describing how this works. Instead, read through these two posts:
Here’s the code:
func sumOfMultiples3And5(max: Int) -> Int {
let three = sumOfMultiplesUsingAP(multiple: 3, max: max)
let five = sumOfMultiplesUsingAP(multiple: 5, max: max)
let fifteen = sumOfMultiplesUsingAP(multiple: 15, max: max)
return (three + five) - fifteen
}
// Using Arithmetic Progression
private func sumOfMultiplesUsingAP(multiple: Int, max: Int) -> Int {
let numberOfMultiples = (max - 1) / multiple
return multiple * numberOfMultiples * (numberOfMultiples + 1) / 2
}
This approach doesn’t use any looping. It’s much more efficient than the brute-force methods. But you need to know about Arithmetic Progressions and how to apply them.
If this were given to me in an interview, I would be satisfied with the brute-force solutions I came up with here. However, if the max number were larger than 1000, I would need to look for a more performant solution. The mathematical version would work well here.
Next up is problem two from the Project Euler website.