# Shaun Abram

Java and Technology weblog

## 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.

```
```

```
```