DEV Community

Michael Caveney
Michael Caveney

Posted on

Problem Solving with Project Euler, Part One: Multiples of 3 and 5

This post will contain potential spoilers/solutions for the first Project Euler problem, so read with caution if you're actively working on it!

What is Project Euler?

According to freeCodeCamp, where I first encountered these problems:

Project Euler (pronounced Oiler) is a series of challenging mathematical/computer programming problems meant to delve into unfamiliar areas and learn new concepts in a fun and recreational manner.

The problems range in difficulty and for many the experience is inductive chain learning. That is, by solving one problem it will expose you to a new concept that allows you to undertake a previously inaccessible problem.

Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

from the Project Euler home page

I'll be working through these to detail how to approach problem-solving, so let's dive into the first problem!

Multiples of 3 and 5

The problem on FCC states:

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 the provided parameter value number.

There is a definite test for reading comprehension here, as the problem states that we need to sum all numbers below the number passed into the function as an argument, so I'm taking that into consideration.

What data do I need to solve this problem? I simply need a list of the aforementioned numbers, and then to add them up. This is a very straightforward problem, but I'll be detailing a more exhaustive process to follow in future blog entries that will be helpful for much more difficult problems.

First, I'm setting up variables in the form of an empty array to push the relevant numbers into:

let numbers = [];
Enter fullscreen mode Exit fullscreen mode

There are a few ways that I could populate the array with the necessary data, and what comes to my mind now is to:

  • Set up a for loop with the iterator value set to the number minus 1, that runs while the iterator is above 2 (this was initially set to zero, but I realized while typing this that there are obviously no positive multiples of 3 or 5 beneath 3, so there's not point in running unnecessary iterations), and subtracts one from the iterator with every pass.

  • The loop will run a check with each pass to see if the modulus of the iterator value and (3 or 5) equals zero. If so, that values gets pushed (read: added to the end of the array) to the numbers array. This looks like:

for (let i = number - 1; i > 2; i--) {
    if (i % 3 == 0 || i % 5 == 0) {
      numbers.push(i);
    }
Enter fullscreen mode Exit fullscreen mode

Finally, I'l going to run the .reduce method on the numbers array, and return that value. Array.reduce() is one of the hairier built-in JavaScript methods to learn, but the short version is that it runs a process over an array to reduce it down to a single value. So the completed code looks like this:

function multiplesOf3and5(number) {
  let numbers = [];

  for (let i = number - 1; i > 2; i--) {
    if (i % 3 == 0 || i % 5 == 0) {
      numbers.push(i);
    }
  }

  return numbers.reduce((a, b) => a + b, 0);
}

multiplesOf3and5(1000);
Enter fullscreen mode Exit fullscreen mode

...and it works!

Final Thoughts

I can do more work here, including analyzing the Big O result of the algorithm, and using that information to improve the runtime. Did you also work on this problem? If so, what did your solution look like?

Top comments (1)

Collapse
 
wil92 profile image
Guillermo • Edited

You should take a look to this en.wikipedia.org/wiki/Inclusion%E2..., because you can solve this problem with O(1) complexity