# Sum All Odd Fibonacci Numbers: maybe alternative approach is worth mentioning?

On the hints page: blurred as a spoiler

both solutions are using check for odd/even like this

``````arrFib.filter(x => x % 2 != 0)
``````

Maybe it’s worth mentioning on the hints page, that when dealing with Fibonacci numbers one could use this property:
Every third number of the sequence is even
relevant wiki, check out divisibility properties section
in order to do some filtering like this, for example:

``````arrFib.filter(
(fib, index) => (index + 1) % 3 !== 0
)
``````

Why don’t you submit your solution here using this method along with a `Code Explanation` as is done on the other two solutions? That way, users can learn about this approach when looking at the solutions. We will add it to the solutions section of the Guide.

1 Like

I will definitely do that. I just wanted to make sure that such solution can be useful, that’s why I asked first.

You can also check if a number is even using bitwise `&` operator:

`!(num & 1)`

or odd:

`!!(num & 1)`

It is also faster than calculating using `mod`.

1 Like

Is it actually faster in Javascript? Since JS doesn’t have a proper integer type, that would be surprising to me.

This is a micro optimization I usually skip since 1) it’s less clear to most readers 2) compilers know how to optimize Mod 2 and 3) any language without an optimization pass probably won’t be used for a task where this difference is large enough to be appreciable.

2 Likes
``````function generateFibsArray(num) {

let fibsArray = [
[1, true],
[1, true]
];

let newFib = [
fibsArray[fibsArray.length - 1] + fibsArray[fibsArray.length - 2],
true
]

while (newFib <= num) {

fibsArray.push(newFib);
newFib = [
fibsArray[fibsArray.length - 1] + fibsArray[fibsArray.length - 2],
true
]

}

return fibsArray;

}

function everyThirdIsFalse(arr) {

for (let i = 2; i < arr.length; i += 3) {

arr[i] = false;

}

return arr;

}

function sumFibs(num) {

let sumOddFibs = 0;
const Fibs = everyThirdIsFalse(generateFibsArray(num));

for (let fib of Fibs) {

if (fib) {

sumOddFibs += fib;

}

}

return sumOddFibs;

}

console.log(sumFibs(1));//2
console.log(sumFibs(1000));//1785
console.log(sumFibs(4000000));//4613732
console.log(sumFibs(4));//5
console.log(sumFibs(75024));//60696
console.log(sumFibs(75025));//135721
``````

## Code Explanation

### General idea

To use property of Fibonacci numbers: every third number in the sequence is even.
To use boolean variables in order to avoid using division.

### Algorithm

• Use function generateFibsArray() to create 2D array. Every element: Fibonacci number <= num, and boolean value set to true

• Flip boolean values to false for every third Fibonacci number, using function everyThirdIsFalse()

• Perform calculations of result in the sumFibs() function

Your solution is relatively heavy, in my personal opinion. I think you can simplify matters if you avoid arrays - the second solution explicitly calls out the fact that dynamically creating arrays is relatively expensive. Here is my effort to simplify while still showing the same idea:

``````function sumFibs(num) {
let f0 = 0;
let f1 = 1;
let f2 = 1;

let sum = 0;
while (f1 <= num) {
// Update sum
// Note: every third Fibonacci number is even
//   and the rest are odd
sum += f1;
if (f2 <= num) sum += f2;

// Compute next three Fibonacci numbers
[f0, f1] = [f1 + f2, f2 + (f1 + f2)];
f2 = f0 + f1;
}

return sum;
}
``````

That said though, I think this would be a cool solution to add to the list of suggested solutions.

1 Like

Yeah, I saw that. But my main intention was to exploit property of Fibs (every 3rd is even) somehow. In the process, I remembered that I also can avoid division here using booleans. To avoid arrays - wasn’t able to figure it out.

This your idea - to generate fibs in groups of three - I couldn’t figure it out on my own, that’s for sure!

If you have thoughts on how to make my solution clearer - please share!

I think this part is the hardest to parse and there are a few ways to write it. I’m not sure which is the clearest.

Well, this is solution for intermediate algo scripting section, right? I personally think, at this stage of curriculum students should be able to understand such lines of code. Maybe I am wrong though.

1 Like

Too many `f[num]`s @JeremyLT It is a cool solution.

1 Like

It still feels a bit like magic in the update part, but maybe this rearranging of comments helps?

``````function sumFibs(num) {
// Every third Fibbonaci number is even
//   and the rest are odd
let f0 = 0;
let f1 = 1;
let f2 = 1;

// Generate triples until num is reached
let sum = 0;
while (f1 <= num) {
// Update sum
sum += f1;
if (f2 <= num) sum += f2;

// Compute next three Fibonacci numbers
[f0, f1] = [f1 + f2, f2 + (f1 + f2)];
f2 = f0 + f1;
}

return sum;
}
``````