Shaun Abram
Technology and Leadership Blog
Project Euler, Problem 1 (in Groovy/Java)
I have been wanting to get up to speed with Groovy for while but hadn’t really found a good excuse. So when I came across Project Euler, I decided to try to solve the problems using Groovy.
I managed to solve Problem#1 today.
Note that I would describe the solutions below as being in Groovy/Java because I still fall back on my old Java habits rather than using all the Groovy language constructs available to me. Anyway…
The problem is:
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.
Unsurprisingly, I took the brute force approach first:
int n = 999, total=0;
for (int i in 1..n) {
if ( (i%3==0) || (i%5==0) ) {
total=total+i;
}
}
println("Total=" + total)
A good first start, but far from perfect as it loops through every number between 1 and n. I could improve it slightly by tweaking the start and end points (e.g. starting at 3), but it would still roughly involve n iterations.
My second attempt was this:
int n = 999, total=0;
Set nums = new HashSet();
for (int i=3; i
Note the use of the HashSet to avoid counting duplicates (i.e. numbers divisible by 3 and 5, like 15, 30 etc). Obviously the code could be tidied up but this reduced the number of loop iterations from 999 to 532 (and the run time from ~110ms to ~90ms).
However, the code/algorithm is still imperfect as although it doesn't count numbers divisible by 3 and 5 twice, it still iterates over them twice. I couldn't figure out a way to avoid this, so having met the requirements (I verified the correct answer on the Euler site and, at ~90ms, it runs well under one second), I submitted my answer and started reading the supplied solution.
The 'perfect' solution involves 3 breakthroughs.
The first is that the ideal solution involves using formulae, not iteration.
The second is that in the example of the total all numbers up to 1000 divisible by 3
i.e.
3+6+9+ ... +999
= 3*(1+2+3+...+1000/3)
where 1000 divided by 3 is rounded down.
The 3rd and final breakthrough required is that:
1+2+3+...+y
= (y/2)*(y+1)
I have to admit that I am not sure I would have ever made these break throughs myself!
But using these facts, the ideal solution is along the following lines:
static int max = 999;
static void main(def args) {
int total = sumDivisibleBy(3)+sumDivisibleBy(5)-sumDivisibleBy(15)
println("\nTotal="+total)
}
static int sumDivisibleBy(n) {
int p=max / n
return n*(p*(p+1)) / 2
}
This solution reduced the run time from ~90ms to ~20ms.
Next up, Problem#2...