Summing all even Fibonacci numbers less than or equal to 4 million

Finding the sum of specific values in a series can be a common interview problem. There are many different forms that an algorithm of this type can take. The one we will be looking at today is the second problem from projecteuler.net, so if you are thinking about working your way through those problems and don’t want any spoilers, you should stop reading for the moment.

The Problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Ok…last warning! Solutions ahead!

The Sudo Code:

Sudo code gives us a non-coding-language-specific way to organize the logical process that our algorithm will follow. It should be written in such a way that someone who is not a developer can understand the basic thought process. Leave the code out for now!

Here is my sudo code:

There are still some terms in there like “array” that are code-speak, but sometimes you can’t get around that. For the most part the above sudo code is pretty readable regardless of coding experience. Now lets see what it looks like to implement it with JavaScript.

The Code:

First we can set up the basic structure based on our sudo code:

function evenFibSum(limit) {
    const fibArray = [1, 2];
    let fibSum = 2;
    while () {
        let fibValue = ;
        fibArray.push(fibValue);
        if () {
            fibSum += fibValue;
        }
    }
    return fibSum;
}

So far this doesn’t look too different from the sudo code. Note that I am passing the parameter “limit” in to evenFibSum. This is not necessary, but it does allow us to generalize the function so that it can be used to find the sum for values other than 4 million as well. It’s never a bad idea to generalize!

Now we just need to add in the logic for creating the next value in the Fibonacci sequence, as well as the conditions for exiting the while loop. Let’s deal with the while loop first. We want to break out of the loop once we have reached a Fibonacci value that exceeds our limit, which in the case of this problem is 4 million. The logic for that looks something like this:

while (fibArray[fibArray.length - 1] <= limit)

In this case we are checking if the last value in fibArray is greater than the limit. If it is, we will break out of our while loop and no more values will be added to fibSum. Next we need to define the logic that finds the next value in the Fibonacci sequence:

let fibValue = (fibArray[fibArray.length - 1]) + (fibArray[fibArray.length - 2]);

Putting this all together and adding the logic for determining whether or not fibValue is an even number, our full function looks like this:

function evenFibSum(limit) {
    const fibArray = [1, 2];
    let fibSum = 2;
    while (fibArray[fibArray.length - 1] <= limit) {
        let fibValue = (fibArray[fibArray.length - 1]) + (fibArray[fibArray.length - 2]);
        fibArray.push(fibValue);
        if (fibValue % 2 === 0) {
            fibSum += fibValue;
        }
    }
    return fibSum;
}

console.log(evenFibSum(4000000));

As you can see, we pass in the value of 4 million as the limit in the function call within the console log. The outcome of this function is 4613732. And there is our solution!

Have you given this problem a try? Did you come up with a different solution? I’d love to see it!