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

Next up, Problem#2...
One of the toughest tasks on a project can be coming up with estimates, so I was interested to see this blog post quoting some of Joel Spolsky‘s thoughts on creating specifications and coming up with quotes for client work, which I think makes a lot of sense. Tags: consulting It’s been a while since I have posted here; The last 2 months have been hectic. I started a new project at work (I’m “Tech Lead”, on site at a major bank here in California, using Java/XML/Spring), took a vacation in Europe, did a best man’s speech at a friends wedding, and completed the Escape From Alcatraz triathlon. Been a busy time! I have a few ideas for upcoming articles, and I am also thinking about taking the Spring Certification exam. If so, I will be sure to post about it here… There is an interesting article on TheServerSide today, about a book called “97 Things Every Software Architect Should Know”. It contains some good articles from some well known authors and architects, all short and easy to read. My personal favorites are## Spec’ing and Pricing Client Projects

## Back from Hiatus

## Things Every Software Architect Should Know

```
```

```
```