Viren Bhagat

Solving "Sum All Odd Fibonacci Numbers" / freeCodeCamp Algorithm Challenges

7/27/2020

Sum All Odd Fibonacci Numbers

Let's solve freeCodeCamp's intermediate algorithm scripting challenge, 'Sum All Odd Fibonacci Numbers'.

Starter Code

function sumFibs(num) {
  return num;
}

sumFibs(4);

Instructions

Given a positive integer num, return the sum of all odd Fibonacci numbers that are less than or equal to num.

The first two numbers in the Fibonacci sequence are 1 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first six numbers of the Fibonacci sequence are 1, 1, 2, 3, 5 and 8.

For example, sumFibs(10) should return 10 because all odd Fibonacci numbers less than or equal to 10 are 1, 1, 3, and 5.

Test Cases

  • sumFibs(1) should return a number.
  • sumFibs(1000) should return 1785.
  • sumFibs(4000000) should return 4613732.
  • sumFibs(4) should return 5.
  • sumFibs(75024) should return 60696.
  • sumFibs(75025) should return 135721.

Our Approach

After reading the starter code, instructions, and test cases, this is what I summarized about this challenge -

  • Our input, num, is an integer.
  • We must return an integer.
  • While figuring out a solution to this, we need to consider to things - Fibonacci numbers and also odd numbers.

Fibonacci numbers, from what I've read, is a common algorithm challenge. What exactly is a Fibonacci number? The instructions provide a concise summary, "The first two numbers in the Fibonacci sequence are 1 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first six numbers of the Fibonacci sequence are 1, 1, 2, 3, 5 and 8."

So we'll always have to work with a pair of numbers. Looking at the above numbers -

1, 1 // 1 + 1 = 2
1, 2 // 1 + 2 = 3
2, 3 // 2 + 3 = 5
3, 5 // 3 + 5 = 8
5, 8 // 5 + 8 = 13
8 + 13 // 8 + 13 = 21
And so on...

Can you recognize the pattern of a Fibonacci sequence looking at the above?

So our challenge gives us one number, we have to find the sum all of all the Fibonacci numbers that are odd. Like other challenges, this will involve a loop for sure. Let's begin with the standard steps.

Since we know the first pair of Fibonacci numbers, we can declare a variable and set it to [1,1] then can check and swap the values out.

let fibs = [1,1];

The next variable we can declare is a count so we can increment it every loop until we reach our limit, num.

let count = 0;

One more variable we will need is something to hold the sum of our current Fibonacci pair. I declared a variable, fibNums, which will be used soon.

So our code looks like this for right now -

function sumFibs(num) {
  let fibs = [1,1]; // first pair
  let count = 0;
  let fibNums;
}

Next step to consider is looping. We'll opt for a while statement, and we will continue to run it while num > count so we can go from 0 to the limit of num since we want to find odd Fibonacci numbers that are less or equal to num.

while statement (MDN)

It will keep running until the statement is not true any longer. So our statement would be while (num > count) since we want to look at all numbers smaller than num. Each loop, we will increase count by 1.

function sumFibs(num) {
  let fibs = [1,1]; // first pair
  let count = 0;
  let fibNums;
  
  while (num > count) {
    // Fibonacci logic stuff here
    count++;
  }
}

Alright, great. So how do we figure out this Fibonacci sequence stuff? We will handle it first then worry about the odd number constraint we have then we can just sum it up and return it.

We will call on the variable, fibNums which we just created. So we will start by setting fibNums equal to our fibs pair.

// First loop, count = 0
fibNums = fibs[count] + fibs[count + 1];

// Equals 2

We will take the fibNums value and add it to fibs array if it is less than num. We will increment count by 1 and it will loop over as it is a while statement. So let's look at that and try the next loop or two.

// First loop, count = 0, fibs = [1,1]
while (num > count) {
    fibNums = fibs[count] + fibs[count + 1];
  
  if (fibNums <= num) {
    fibs.push(fibNums);
  }
  
  count++;
}
// fibNums now has a value of 2 since fibNums = fibs[0] + fibs[0 + 1];

// Second loop, count = 1, fibs = [1, 1, 2], fibNums = fibs[1] + [1+1];
// Third loop, count = 2, fibs = [1, 1, 2, 3], fibNums = fibs[2] + [2+1];
// Fourth loop, count = 3, fibs = [1, 1, 2, 3, 5], fibNums = fibs[3] + [3+1];
// Fifth loop, count = 4, fibs = [1, 1, 2, 3, 5, 8], fibNums = fibs[4] + [4+1];
// And so on...

So that will get us all the Fibonacci numbers less than our num.

Our remaining two steps are to get the odd Fibonacci numbers and then sum them to return one value. Since fibs is an array, we can look at some of the new-er higher order methods to see if we can get the odd numbers only. I'm looking at you, filter().

Array.filter() on MDN

We just implement a test case and each index that passes is created into a new array. So to find odd numbers, we can use the modulo operator.

fibs.filter(n => n % 2 !== 0)

We will create a new array of items that pass the above test. If the number divided by two has a remainder (an odd number), we will keep that item. For example,

[1, 2, 3, 4, 5, 6, 7, 8].filter(n => n % 2 !== 0)
// Array(4) [ 1, 3, 5, 7 ]

Alright great, we will be able to obtain all the odd Fibonacci numbers. The last step is to sum them all. There is another array method we can use, reduce().

Array.reduce() on MDN

MDN gives us a small but understandble example IMO.

const array1 = [1, 2, 3, 4];
const reducer = (accumulator, currentValue) => accumulator + currentValue;
// 1 + 2 + 3 + 4
console.log(array1.reduce(reducer));
// expected output: 10

We can actually chain this method on to our filter() method.

fibs.filter(n => n % 2 !== 0).reduce((a,b) => a + b);

Make sure to return.

Our Solution

function sumFibs(num) {
  let fibs = [1, 1];
  let count = 0;
  let fibNums;

  while (num > count) {
    fibNums = fibs[count] + fibs[count + 1];
    
    if (fibNums <= num) {
      fibs.push(fibNums);
    }

    count++;
  }

  return fibs.filter(n => n % 2 !== 0).reduce((a,b) => a + b);

}

Links & Resources

'Sum All Odd Fibonacci Numbers' Challenge on fCC

freeCodeCamp

Donate to FCC!

Solution on my GitHub

Thank you for reading!

fcc, javascript, algorithms