I just discovered Project Euler and found it fascinating. There is joy in solving the problems. Once I solved them I was on the lookout for any interesting ways of solving the same problem. There are plenty of blogs out there giving direct solutions to the problems. That is not what I was looking for. Very few seem to focus on the learning process behind the problems or allied topics. So I thought, why not share mine and see how it goes.
Problem 1
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.
Brute force seems so easy for this problem. Here is the solution in Ruby
max = 1000
all_multiples = Array.new
(1..max).each do | num |
all_multiples << num if num.modulo(3) == 0 || num.modulo(5) == 0
end
sum = all_multiples.reduce(:+)
This is fine for 2 multiples with the maximum set to 1000. However the complexity will quickly shoot up with increase in max and the number of multiples. A generic routine like the following will take O(m*n) to execute where m is number of primes and n is the maximum number.
With project Euler all problems usually have a short cut way because the intent is to solve in a minute or so. However I did not have the trick yet, so I first optimized the brute force method.
Optimization 1. You don't have to go through all the numbers from 1 to 1000. You just need the multiples.
max = 1000
i = 1
primes = [3,5]
primes.each do | cur_prime |
loop{
num = i*cur_prime;
break if num > max;
i += 1
all_multiples << num
}
sum = all_multiples.uniq.reduce(:+)
This reduces the loop complexity a bit. But the uniq at the end is a killer. It needs to sort the numbers before it can make the array unique. So we still have a reasonably high complexity.
Optimization 2
How about we do not insert the number at all into the array if it is already present? A nice way to do it would be insertion sort. While inserting we keep track of the last point of insertion and then insert the number only if it is not already present in the remainder of the array.
primes=[3,5]
max = 1000
multiples = Array.new
primes.each do | cur_prime |
i = 1
last_insertion_at = 0
loop{
mul = i*cur_prime
break if mul > max
inserted = false
# Start from the last insertion location
(last_insertion_at...multiples.length).each do | loc |
next if multiples[loc] < mul
break if multiples[loc] == mul
inserted = true
multiples.insert(loc, mul)
last_insertion_at = loc
break
end
if !inserted
multiples << mul
last_insertion_at = multiples.length - 1
end
i += 1
}
end
sum = multiples.reduce(:+)
Now that is much much faster than previous code. A small trick that can be used to improve this further is to sort the primes array and then run its loop inside the second loop rather than outside. That ensures the insertion at any point moves a smaller number of numbers. However it still has to do a lot of data moving and not much better.
Optimization 3:
You could simplify by using a hash here. Mostly it will be implemented using a tree and is sparse.
primes.each do | prime |
i = 0
loop{
mul = i*prime
break if mul > max
i += 1
multiples[mul] = mul
}
end
sum = multiples.reduce(:+)
You get simpler code and increased speed at cost of memory. However you still have to run a large loop.
The killer optimization: Using some lateral thinking
The biggest improvement comes from realizing that you only need the sum. Not the actual multiples themselves. Aha! Now that is a revelation. The sum of all multiples of a number up-to a maximum is the number multiplied by a simple sum of consecutive numbers up-to some n. We know sum of n consecutive numbers is n * (n+1)/2. So first lets solve it for 2 numbers say 2 and 3. We get the following
def sum_of_multiples(max_number, prime)
n = max_number / prime
return prime * (n * (n+1) ) / 2
end
sum = sum_of_multiples(max, 2) + sum_of_multiples(max, 3)
- sum_of_multiples(max, 6)
You have to subtract multiples of 6 because they got added twice. This is so much faster. Constant time for whatever max number you have. Its complexity is O( number_of_primes ).
Having solved it this way, I was interested in solving it for any number of primes. So now if we have 3 primes instead of 2, say 2,3 and 5 what do we do? We need to be careful here. The answer is
sum = sum_of_multiples(max, 2) + sum_of_multiples(max, 3)
+ sum_of_multiples(max, 5)
- sum_of_multiples(max, 6) - sum_of_multiples(max,15)
- sum_of_multiples(max,10)
+ sum_of_multiples(max,30)
There is a addition of combinations of length 1, subtraction of all combinations of length 2 and addition of combination of length 3. The pattern is now clear. The generic solution would be
multiples = [2,3,5]
sign = 1
sum = 0
max = 1000
multiples.length.times do | l |
local_sum = 0
multiples.combination(l + 1).each do | combination |
local_multiple = combination.reduce(:*)
local_sum += sum_of_multiple(max, local_multiple)
end
sum += (sign * local_sum)
sign = -sign
end
Ruby gives a neat combination function. However most other languages will not. Here is a recursive way of getting the combinations.
# Better to ruby's inbuilt Array.combination.
# This is just for learning.
def combinations(array, k)
return [array] if array.length == k
return [array.first] if k == 1
my_combinations = []
array.length.times do | i |
new_array = array[i+1..-1]
element = array[i]
local_combinations = combinations( new_array, k-1 )
local_combinations.each do | one_combination |
my_combinations << [element] + one_combination
end
end
my_combinations
end
You need not store the combinations and can yield on each one instead.
This gives us generic code to calculate sum of multiples for any X primes upto a max number.
The complexity of the original problem becomes the complexity of finding all combinations of all lengths of the elements in an array.
