Sum All Odd Fibonacci Numbers: my solution works, but I don't know why πŸ˜…

Sum All Odd Fibonacci Numbers: my solution works, but I don't know why πŸ˜…
0

#1

Title says it all, really. I wrote it myself, and in some sort of way it makes sense, but there is 0% chance I could explain this to anyone else. I can’t even explain it to myself, to be honest :sweat_smile:can someone tell if this solution really is correct (if so, why?) or if it just happened to pass the tests?
Thanks!

function sumFibs(num) {
  let fib = [1, 1];
  
  for (let i = 0; fib[i] <= num - fib[i + 1]; i++) {
    fib.push(fib[i] + fib[i + 1]);
  }

return fib.filter((num) => num % 2 === 1).reduce((a, b) => a + b);
}

sumFibs(4);

#2

So you start with a value for num - say 10.

Fibonacci sequence adds the previous two numbers in the sequence together - 0 + 1 is 1, 1 + 1 is 2, 1 + 2 is 3, 2 + 3 is 5 and so on.

So the fib array starts at [1, 1]: it’s always an array with at least two elements, and those two elements have to be the start of the sequence (can be 0 and 1, makes no difference to the end result).

The loop starts with a counter i at 0. It’s going to stop when num - fib[i + 1] is > fib[i]: ie when the target number minus the last element in the array is greater than the second-last element in the array.

The aim of the loop is to add a value to fib on each iteration, and it’s going to move through the the array and look at the value behind that.

So num is 10, fib is [1,1], i is 0

fib[i] <= num - fib[i + 1]
1 <= 10 - 1
true
// so
fib.push(fib[i] + fib[i + 1])
fib.push(1 + 1)
fib.push(2)

So num is 10, fib is [1,1,2], i is 1

fib[i] <= num - fib[i + 1]
1 <= 10 - 2
true
// so
fib.push(fib[i] + fib[i + 1])
fib.push(1 + 2)
fib.push(3)

So num is 10, fib is [1,1,2,3], i is 2

fib[i] <= num - fib[i + 1]
2 <= 10 - 3
true
// so
fib.push(fib[i] + fib[i + 1])
fib.push(2 + 3)
fib.push(5)

So num is 10, fib is [1,1,2,3,5], i is 3

fib[i] <= num - fib[i + 1]
3 <= 10 - 5
true
// so
fib.push(fib[i] + fib[i + 1])
fib.push(3 + 5)
fib.push(8)

So num is 10, fib is [1,1,2,3,5,8], i is 4

fib[i] <= num - fib[i + 1]
5 <= 10 - 8
false
// loop ends

fib is now [1,1,2,3,5,8]. Filter that for odd numbers, then sum.


#3

This was a thorough and completely understandable explanation. Thank you so much! If I could like this more than once, I would. Much appreciated! :pray:


#4

If you want to optimise this, you can drop the fibs array, and the filter/reduce. If you have a variable each for the previous and current values, and a variable that holds the total (which would start as the previous value). You can use the logic almost as is, but instead of pushing to the array, just increment the current/previous on every iteration, and add to the total if the current value is odd. It’ll take a little bit of fiddling around with, but should simplify the code slightly


#5

Is it better stylistically to have several variables instead of chaining methods? I thought the general rule of thumb was that fewer lines are better?

I know that it comes down to opinion and individual/team preference at some point, but I mean just generally.


#6

Its not really related to chaining methods - what you are doing is:

  1. Creating an empty array
  2. Pushing values to that array via a loop (which could involve a huge amount of values)
  3. Filtering that array (full pass through the array)
  4. Reducing the array (second full pass through the array)

By just having three variables, you go to

  1. Update three variables (each just a number) in the loop, then return one of them (the end product)

Less code is good, as there are less likely to be errors, but in this case it isn’t actually likely to mean less code, and there are far fewer operations.


#7

ahhhh understood. Thanks for the clarification!