In this series, we'll be solving Project Euler problems. First using brute force approach(if possible), then using optimized approach. Let's get started!
Project Euler Problem 1 states that:
Let's make it more generic, instead of finding the sum of all the multiples of 3 or 5 below 1000, let's find the sum for any number. The number could range from 0 to millions. Our program should be able to handle it. We will verify this behavior with test cases.
Okay! I'm going to take object oriented approach here to organize the code, but feel free to skip the object oriented part, if you are not cool with it.
Let's quickly add the basic skeleton.
Our test skeleton
Let's go through each chunk of code one by one.
First of all, we have a DivisibleBy3And5 class, which is taking a number on initialization and storing it @number instance variable, so that we don't have to pass the number around to each method.
Next we have 'sum method, which currently just returns a static value(23).
Moving on to our test code. The numbers method is just there to initialize our class DivisibleBy3And5 so that we can use simply pass number to our numbers method, have it return an instance of our DivisibleBy3And5 class so, that we could easily call our other instance methods like sum to get the sum. This approach makes our test code concise and easier to read.
Our skeleton looks good and gives a clear picture of the overall system, but it's not very useful, so let's make it more useful.
And our test suite:
Run the tests and it's passing. Great!
This was simple enough. Our brute force approach helped us get started with the problem in hand without getting overwhelmed, but we can optimize this to improve performance.
What's the complexity of our brute force approach, you asked? Given the number N, we are iterating through each number, incrementing sum by adding the number, if the number is divisible by either 3 or 5.
Checking if the number is divisible by 3 or 5 takes constant time, so does the adding number to sum variable, but we are performing N number of constant operations for a given number N, so the big-oh complexity of our brute force approach is O(N). Simple!
Hint: It's a mathematical problem, so it involves some kind of mathematical expression.
Okay! Let's start breaking down the problem statement.
List all the numbers below the number N that are multiples of 3 or 5. Let me rephrase it. List all the numbers below the number N that are multiples of 3
3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...
or all the numbers below the number N that are multiple of 5
5, 10, 15, 20, 25, 30, 35, 40, ...
There are two things to notice here.
See, how dividing problem into smaller pieces, makes the solution easier?
Enough Math! Let's write some code.
Everything looks simple enough except calculate_sum method, which requires some explaining.
For number 100, the value of N would be 99, as it's the largest number, which is divisible by 3 and is still less than 100. So, to the sum for S3 series would be (3 + 6 + 9 + ... + 99), since 3 is common we can extract it, so our series becomes 3 * (1 + 2 + 3 + 4 + ... + 33).
Now the (1 + 2 + 3 + 4 + ... + 33) part is particularly interesting. It forms a sequence of first N numbers, where N is 33. What's the sum of first N natural numbers? It is N(N+1)/2. So, to calculate the sum of (3 + 6 + 9 + ... + 99), we are simply multiplying 3 to N(N+1)/2, which is exactly what we are doing at line 15.
So, to achieve all of this, we are calculating the largest natural number for 1 + 2 + 3 + ... series at line 14, at line 15 we are simply multiplying divisor(3, 5 or 15) by N(N+1)/2 to get the sum of original series.
Using this approach we have been able to avoid iterating over N numbers, which results in constant time complexity i.e O(1). With our new and optimized code, we can easily handle millions of numbers.
PS: The code listed in this blog post is hosted on Github. Feel free to propose any change by submitting a pull request or by opening an issue.
Project Euler Problem 1 states that:
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.
Let's make it more generic, instead of finding the sum of all the multiples of 3 or 5 below 1000, let's find the sum for any number. The number could range from 0 to millions. Our program should be able to handle it. We will verify this behavior with test cases.
Okay! I'm going to take object oriented approach here to organize the code, but feel free to skip the object oriented part, if you are not cool with it.
Let's quickly add the basic skeleton.
class DivisibleBy3And5
def initialize(number)
@number = number
end
def sum
23
end
end
Our test skeleton
describe "divisible by 3 or 5" do
def numbers(number)
DivisibleBy3And5.new(number)
end
it "should return 23" do
expect(numbers(10).sum).to eq(23)
end
end
Let's go through each chunk of code one by one.
First of all, we have a DivisibleBy3And5 class, which is taking a number on initialization and storing it @number instance variable, so that we don't have to pass the number around to each method.
Next we have 'sum method, which currently just returns a static value(23).
Moving on to our test code. The numbers method is just there to initialize our class DivisibleBy3And5 so that we can use simply pass number to our numbers method, have it return an instance of our DivisibleBy3And5 class so, that we could easily call our other instance methods like sum to get the sum. This approach makes our test code concise and easier to read.
Our skeleton looks good and gives a clear picture of the overall system, but it's not very useful, so let's make it more useful.
Brute Force Solution
class DivisibleBy3And5
def initialize(number)
@number = number
end
def sum
return 0 if @number < 3
calculate_sum
end
def calculate_sum
sum = 0
(3..@number-1).each do |number|
sum += number if divisible?(number)
end
sum
end
def divisible?(number)
number % 3 == 0 || number % 5 == 0
end
end
And our test suite:
describe "divisible by 3 or 5" do
def numbers(num)
DivisibleBy3And5.new(num)
end
it "should return 23" do
expect(numbers(10).sum).to eq(23)
end
it "should return 2318" do
expect(numbers(100).sum).to eq(2318)
end
end
Run the tests and it's passing. Great!
This was simple enough. Our brute force approach helped us get started with the problem in hand without getting overwhelmed, but we can optimize this to improve performance.
What's the complexity of our brute force approach, you asked? Given the number N, we are iterating through each number, incrementing sum by adding the number, if the number is divisible by either 3 or 5.
Checking if the number is divisible by 3 or 5 takes constant time, so does the adding number to sum variable, but we are performing N number of constant operations for a given number N, so the big-oh complexity of our brute force approach is O(N). Simple!
Optimized Approach
Step back for a moment, and think about the problem. Does it follow some kind of pattern? I'll let you think before proceeding.Hint: It's a mathematical problem, so it involves some kind of mathematical expression.
Okay! Let's start breaking down the problem statement.
List all the numbers below the number N that are multiples of 3 or 5. Let me rephrase it. List all the numbers below the number N that are multiples of 3
3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...
or all the numbers below the number N that are multiple of 5
5, 10, 15, 20, 25, 30, 35, 40, ...
There are two things to notice here.
- Each sequence(let's call it S3 & S5) forms a series called arithmetic series.
- They have some numbers in common. 15, 30, 45, 60, ... in other words they have an arithmetic series in common with the difference between each element being(d) 15 and first element being 15(a).
So we need to add the sum of first series(S3) & sum of second series(S5) and finally subtract the sum of third series(S15) from the sum of first two(i.e. S3 & S5).
In mathematical term, it can be represented as Sum of S3 + Sum of S5 - Sum of S15
See, how dividing problem into smaller pieces, makes the solution easier?
Enough Math! Let's write some code.
class DivisibleBy3And5
def initialize(number)
@number = number
end
def sum
calculate_sum(3) + calculate_sum(5) - calculate_sum(15)
end
def calculate_sum(divisor)
n = (@number - 1).div divisor
divisor * n * (n + 1)/2
end
end
Everything looks simple enough except calculate_sum method, which requires some explaining.
For number 100, the value of N would be 99, as it's the largest number, which is divisible by 3 and is still less than 100. So, to the sum for S3 series would be (3 + 6 + 9 + ... + 99), since 3 is common we can extract it, so our series becomes 3 * (1 + 2 + 3 + 4 + ... + 33).
Now the (1 + 2 + 3 + 4 + ... + 33) part is particularly interesting. It forms a sequence of first N numbers, where N is 33. What's the sum of first N natural numbers? It is N(N+1)/2. So, to calculate the sum of (3 + 6 + 9 + ... + 99), we are simply multiplying 3 to N(N+1)/2, which is exactly what we are doing at line 15.
So, to achieve all of this, we are calculating the largest natural number for 1 + 2 + 3 + ... series at line 14, at line 15 we are simply multiplying divisor(3, 5 or 15) by N(N+1)/2 to get the sum of original series.
Using this approach we have been able to avoid iterating over N numbers, which results in constant time complexity i.e O(1). With our new and optimized code, we can easily handle millions of numbers.
PS: The code listed in this blog post is hosted on Github. Feel free to propose any change by submitting a pull request or by opening an issue.
