# Some tips for solving problems

Let's solve the first Euler problem:

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

## Understand the problem

Make sure you fully understand what you're supposed to be doing.  Check anything you're not sure about.

**Q.** What's a "natural number?"

**A.** the positive integers (whole numbers) 1, 2, 3, etc., and sometimes zero as well.

**Q.** What's a mutliple?

**A.** a number that may be divided by another a certain number of times without a remainder.

## Try and solve the problem on paper (or a subset of the problem)
Let's do it for the natural numbers below 10:

- Take the number 1: can 1 be divided by 3 or 5 with no remainder?  No, so forget about it.
- Take the number 2: can 2 be divided by 3 or 5 with no remainder?  No, so forget about it.
- Take the number 3: can 3 be divided by 3 or 5 with no remainder?  **Yes**, so write it down.
...
- Take the number 3: can 9 be divided by 3 or 5 with no remainder?  **Yes**, so write it down.

By now we should have written down **3, 5, 6 & 9**

Finally, add them all up to get the sum: **23**

## Try and write out instructions (in human language) that explain how to solve the problem
Imagine you're explaining it to someone who doesn't know anything about coding, they don't know what a condition or a loop is.  Keep it simple.  This is my attempt:

- For every number below 10:
- Take that number and divide it by 3, does the answer have a remainder?  If it does not, then write it down.
- Take the same number and divide it by 5, does the answer havea remainder?  If it does not, then write it down.

Once you have finished this:
- Add up all of the numbers you have written down.

Let's do it again with a little more detail:

- For the number 1:
-- Take that number and divide it by 3, does the answer have a remainder?  If it does not, then write it down.
-- Take the same number and divide it by 5, does the answer havea remainder?  If it does not, then write it down.
- Do the same for the number 2
- Do the same for the number 3,
- Repeat until the number 9

## Look for familiar patterns

Is this problem similar to ones you've solved before?  Can you use the same approach?  Sometimes a keyword in the question can give away what you need to do.

Examples:
- Finding the **sum** or **count** of an array of numbers usually means you'll need a for loop.
- Reading input **until** the user enters a certain character usually means you'll need a while loop.

## Now try and write the code
Break down the task into smaller goals, and then do those one at a time.  These can be whatever makes sense for you, but try to make very small incremental changes.  Here are mine:

### Goal 1: Output the natural numbers below 10

```javascript
for(var i = 1; i < 10; i++) {
  console.log(i);
}
```

### Goal 2: Output the natural numbers below 10 that are multiples of 3

```javascript
for(var i = 1; i < 10; i++) {
  if (i % 3 === 0) {
    console.log(i);
  }
}
```
### Goal 3: Output the natural numbers below 10 that are multiples of 3 or 5

```javascript
for(var i = 1; i < 10; i++) {
  if (i % 3 === 0 || i % 5 === 0) {
    console.log(i);
  }
}
```

### Gosl 4: _Record_ the natural numbers below 10 that are multiples of 3 or 5
```javascript
var multiples = [];

for(var i = 1; i < 10; i++) {
  if (i % 3 === 0 || i % 5 === 0) {
    multiples.push(i);
  }
}

console.log(multiples);
```

### Goal 5: Calculate the sum of the natural numbers below 10 that are multiples of 3 or 5
```javascript
var multiples = [];

for(var i = 1; i < 10; i++) {
  if (i % 3 === 0 || i % 5 === 0) {
    multiples.push(i);
  }
}

var sum = 0;

for(var i = 0; i < multiples.length; i++) {
  sum += multiples[i];
}

console.log(sum);
```
### Goal 6 (The final answer): Calculate the sum of the natural numbers below 1000 that are multiples of 3 or 5
```javascript
var multiples = [];

for(var i = 1; i < 1000; i++) {
  if (i % 3 === 0 || i % 5 === 0) {
    multiples.push(i);
  }
}

var sum = 0;

for(var i = 0; i < multiples.length; i++) {
  sum += multiples[i];
}

console.log(sum);
```

## Optimize your solution (but ONLY if you need to)

The solution above produces the correct answer and, on my PC, it runs in 0.054s, that's definitely good enough, so I would stop here.

However, what if I need to find the sum of all the multiples of 3 or 5 below 1,000,000,000?

The following code crashes on my computer as it runs out of memory:

```javascript
var multiples = [];

for(var i = 1; i < 1000000000; i++) {
  if (i % 3 === 0 || i % 5 === 0) {
    multiples.push(i);
  }
}

var sum = 0;

for(var i = 0; i < multiples.length; i++) {
  sum += multiples[i];
}

console.log(sum);
```

So we would need to optimize it.  Let's try and figure it out.

I'm pretty sure that the problem is the **multiples** array.  It's probably getting pretty big and taking up a lot of space.  What can we do about it?

One pattern that I recognize is we have one loop that creates the array, then another loop that reads from it.  Often this means we can do the whole process in a single loop.  Also I don't care about the contents of **multiples** I only care about the sum.  So I should be able to get rid of multiples completely by keeping a running total:

```javascript
var sum = 0;

for(var i = 1; i < 1000000000; i++) {
  if (i % 3 === 0 || i % 5 === 0) {
    sum += i;
  }
}
console.log(sum);
```