JavaScript Coding Challenge #1 ~ Follow up

A few days ago I posted a simple JavaScript solution for a problem from the Project Euler website called: Multiples of 3 and 5. You can read more about it here.

I was really happy to see that people enjoyed it, and I even had someone who wrote another solution for the problem on the FCC forum, so I decided to write another post solving the same problem but in a different way. This time using a little math ^_^ .

But before that, let’s take a moment and explain why would you want to create another solution for the same problem. You might ask: Isn’t already solved? Why would you want to waste more solving it again?

I can think of at least 2 reasons why you would want to do that:

1. It’s always a very good practice to solve the same problems in 2, 3 or more different ways, because this really pushes you to understand the problem, and each time you do that, you get better and better, thus you’re getting more experience overall. This could be a very useful skill set for the future.
2. Most likely the first time solving a problem won’t get you the best solution, and the time invested in re-thinking another way to solve the same problem will pay off big later.

The new approach

Today we’re going to study another approach that will drastically decrease the time of execution of the algorithm — also the complexity/performance of it. To understand what I mean, let’s find out what is currently the performance of the algorithm: The so called Big O Notation. I highly recommend you look into it.

Let’s see the algorithm we had and what it’s performance is:

function sumOfMultiples(number) {
    let sum = 0;
    for(let i=1; i<number; i++) {
        if(i % 3 === 0 || i % 5 === 0){
            sum += i;
        }
    }
    return sum;
}

As you can see, we have a linear growth of O(n) where n is the number, the parameter of our function. The bigger the number is, the more time is needed for the program to finish.

Let’s say we need 10ms to run an iteration of the for loop. That means that if we loop 1000 times, we’ll need 1000 * 10ms = 10 seconds. If we loop 10,000 times the program will execute for 10000 * 10ms = 100 seconds.

While this isn’t that bad, how awesome would it be if we could get a O(1) algorithm, meaning that it will execute in the same time regardless of the size of the input?

Well, we can… But we’re going to use some math for that to happen! :D

The new solution

To make this easier to understand, first we’re going to simplify the problem:

Find the sum of all numbers from 1 to n.

Of course we can do this easily with a for loop, right? But then we would still have a performance of O(n) which is not what we want. Our goal is to change the approach to get to O(1), and as I said we’re going to use math for that. In this situation we’ll need the: Sum of the First n Natural Numbers formula:

Sum of the First n Natural Numbers

So elegant! Let’s test it:

• for n = 6 we’ll have: (6 * (6 + 1)) / 2 => (6 * 7) / 2 => 42 / 2 which is equal to 21.
• for n = 10 we’ll have: (10 * (10 + 1)) / 2 => (10 * 11) / 2 => 110 / 2 which is equal to 55.

That’s exactly what we want! So simple, yet so powerful! Do you see how we reduced from O(n) to O(1)?

Perfect! Now we can get back to our initial problem: Multiples of 3 and 5.

As you might of noticed, we have a formula which gives us the sum of the first n numbers, all of them, but we only need the sum of the numbers evenly divisible with 3 and the sum of the numbers evenly divisible with 5. That’s not really a problem; we can tweak the formula to fulfill our needs:

For the 3's we’re going to have:

And as you guessed for the 5’s we’re going to have:

S5 = 5 * ((n / 5) * (n / 5 + 1)) / 2.

Awesome! We now have S3 and S5, that means we just need to add them up like this: S = S3 + S5 and we’ll get the correct answer for our problem, right?

Well… actually it’s not quite good. I’ll show you why. Let’s dig deeper to see exactly what S3 and S5 contains:

• S3 = 3 + 6 + 9 + 12 + 15 + 18 + 21 + … + 30 + … + 45 …
• S5 = 5 + 10 + 15 + 20 + 25 + 30 + … + 45 + …

Interesting… We get 15, 30, 45, … Twice! That’s not ok, right? Because we have in our if statement the OR operator:

if (i % 3 === 0 || i % 5 === 0){ // code here }

That means we only need 15, 30, 45, … once. The simplest solution is to subtract all the numbers that are evenly divisible with 15 from our total sum S:

S = S3 + S5 — S15 where S15 = 15 * ((n / 15) * (n / 15 + 1)) / 2.

Congratulations! Now we have that O(1) algorithm we discussed so much about. Let’s now implement it in JavaScript and we’re done:

JavaScript solution

Let’s write a function which will return the sum of all numbers that are evenly divisible by k, where k in our case is: 3, 5 and then 15.

function sumK(numbers, k){
    var div = Math.floor(numbers / k);
    return (k * div * (div + 1)) / 2;
}

We used Math.floor() which rounds a the division downwards to the nearest integer. (For example if we have 10 / 3, we’ll have the result 3, instead of 3.33333). Now we’ll add our sumOfMultiples function and rewrite it as follows:

function sumK(n, k){
    var div = Math.floor(n / k);
    return (k * div * (div + 1)) / 2;
}
function sumOfMultiples(numbers) {
    return sumK(numbers, 3) + sumK(numbers, 5) - sumK(numbers, 15);
}

Note: The new solution will give us the sum of all numbers evenly divisible by 3 or 5 including the last one (numbers). If we want to exclude it, we need to subtract one before calling the sumK functions: numbers -= 1. For the simplicity of the algorithm, I’m going to let it as it is for now :) .

Let’s test it:

sumOfMultiples(10); // returns 33 => 3 + 5 + 6 + 9 + 10
sumOfMultiples(15); // returns 60 => 3 + 5 + 6 + 9 + 12 + 15

Perfect! Congratulations! You did it! :D

Conclusion

Math is awesome. I think that as software developers we can achieve so much more with the help of it. Even though it might look hard or scary sometimes, we’ll never truly evolve doing the easiest part over and over. There is a point in our lives when we need to get out of our comfort zone because that’s the moment when we’ll unleash our true potential!

I hope all of you get the opportunity to get out of your comfort zone and put on your math boots.

If you liked my post, I would sincerely appreciate a click on the Recommend button. 💚