## DEV Community

Viren B

Posted on • Originally published at virenb.cc

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

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

• 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);

}
``````

'Sum All Odd Fibonacci Numbers' Challenge on fCC

freeCodeCamp

Donate to FCC!

Solution on my GitHub

You can do it faster to use Generator / Iterator, not Array:

``````const oddFibG = function*(){
let l = 0
let m = 1
while(true){
[l, m] = [m, l + m]
if ( l % 2 === 1 ) yield l
}
}

const sumFibs = n => {
let sum = 0
for ( const i of oddFibG() ) {
if ( i > n ) return sum
sum = sum + i
}
}
``````

Akash Kava

There is no point in calculating fib of old numbers, you can save it instead of calculating each time.

tatsuo fukuchi

Oh yes, I think so!
How do you like this?:

``````const memoizer = inits => rule =>{
const memo = [...inits]
const elem = n =>
n >= memo.length ? memo[n] = rule(elem)(n)
: memo[n]
return elem
}

const fib =
memoizer( [0, 1] )( a => n => a(n-1) + a(n-2) )

const oddFibG = function*(){
let i = 0
let value
while (true){
value = fib(i)
if (value % 2 === 1) yield value
i = i + 1
}
}

const sumFibs = n => {
let sum = 0
for ( const i of oddFibG() ) {
if ( i > n ) return sum
sum = sum + i
}
}
``````

It's a little more complex, but very much faster than the above.