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][0] + fibsArray[fibsArray.length - 2][0],
    true
    ]
  
  while (newFib[0] <= num) {
    
    fibsArray.push(newFib);
    newFib = [
    fibsArray[fibsArray.length - 1][0] + fibsArray[fibsArray.length - 2][0],
    true
    ]
    
  }
  
  return fibsArray;
  
}

function everyThirdIsFalse(arr) {
  
  for (let i = 2; i < arr.length; i += 3) {
    
    arr[i][1] = false;
    
  }
  
  return arr;
  
}




function sumFibs(num) {
  
  let sumOddFibs = 0;
  const Fibs = everyThirdIsFalse(generateFibsArray(num));
  
  for (let fib of Fibs) {
    
    if (fib[1]) {
      
      sumOddFibs += fib[0];
      
    }
    
  }
  
  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 :grin:

@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;
}