Shaun Abram

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<n+1; i=i+3) {
    if (nums.add(i)) total=total+i;
}
for (int i=5; i<n+1; i=i+5) {
     if (nums.add(i)) total=total+i;
}
println("Total="+total)

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…

Tags: euler, groovy