JavaScript Challenge - Fibonacci Finder

This was my go at it.

const fibFinder = n => { let fibArr = [0, 1]; for(let i = 2; i <= n; i++){ fibArr.push(fibArr[i-2] + fibArr[i-1]); } return fibArr[n]; } console.log(fibFinder(6)) // Leave this so that we can test your code: module.exports = fibFinder;
function fibFinder(n) {
  // Write your code here
  let count = 1
  let first = 0
  let second = n === 0 ? 0 : 1
  while (count < n) {
    count ++
    let newNum = first + second
    first = second
    second = newNum
  }
  return second
}

console.log(fibFinder(0))

// Leave this so that we can test your code:
module.exports = fibFinder;

function fibFinder(n) {
// Write your code here
let num1 = 0;
let num2 = 1;
let result = n;

for(let i = 2; i <= n; i++){
result = num1 + num2;
num1 = num2;
num2 = result;
}
return result;
}
console.log(fibFinder(6))

// Leave this so that we can test your code:
module.exports = fibFinder;

The only correct way to do this.

const fibFinder = (n) => Array(n).fill(0).reduce((a, _, i) => a.push(a[i] + a[i + 1]) && a, [0, 1])[n];

That is an indefensible statement and could not be farther from the truth.

2 Likes

While I enjoy condensing functions into a single line of code just to see if it’s possible, very seldom are one-liners the most efficient in terms of time or space complexity.

3 Likes
function fibFinder(n) { // Write your code here // Formula: Fn = (Fn - 1) + (Fn - 2) let fibNumbers = new Array(n); //Seed fibNumbers array fibNumbers[0] = 0; fibNumbers[1] = 1; for (let i = 2; i <= n; i++) { fibNumbers[i] = fibNumbers[i - 1] + fibNumbers[i - 2]; } return fibNumbers[n]; } console.log(fibFinder(6)) // Leave this so that we can test your code: module.exports = fibFinder;

Do we want a list of Fibonacci numbers, or do we want an answer to the question, what is the Nth term in the sequence? Think on this. What solution code is the best fit?

If the Nth term is what we are after then it makes sense to just run out the sequence to that term and call it a day. There will be very little memory use and we will have our answer.

Of course we can bring out the root five solution, but that’s paper not computer. Let’s not blur the lines. Still, I love paper and pencil.

1 Like

Hi, here is my solution

function fibFinder(n) {
  let a = 0;
  let b = 1;

  for(i = 0; i < n; i++) {
    [a, b] = [b, a + b];
  }
  
  return a;
}
3 Likes

function fibFinder(n) {
if (n < 0) {
return ‘Index must be greater than or equal to zero’
} else if (n <= 1) {
return n
}
let arr = [0, 1];
while (arr.length < (n + 1)) {
arr[arr.length] = arr[arr.length - 1] + arr[arr.length -2]
}
return arr[n]
}

console.log(fibFinder(6))

// Leave this so that we can test your code:
module.exports = fibFinder;

  1. Recursion will keep a lot of memory in call stack until it release stack after end. More and more with any next step
  2. Recursion limited 5000-100000 deep levels depending on engine. Therefore, it is impossible to calculate, for example, 10000th Fibonacci number in Chrome browser. But it is not so important because fibFinder(1477) = Infinity
  3. This approach 5x+ slower than straightforward method with values swapping

This approach 5x slower than fastest

My like to your solution. It will be 3x+ faster with simple swapping.

function fibFinder(n) {
  let a = 0;
  let b = 1;
  let fib;
  for (let i = 0; i < n; i++) {
    fib = a + b;
    a = b;
    b = fib;
  }
  return a;
}
function fibFinder(n) {
  // Write your code here
  if(n==0){
    return 0;
  }

  if(n==1){
    return 1;
  }

  return(fibFinder(n-2)+ fibFinder(n-1));
}

console.log(fibFinder(6))

// Leave this so that we can test your code:
module.exports = fibFinder;
1 Like

just calculate the next term and push it to an array until the array has n terms

function fibFinder(n) {
  // Write your code here
  let fibArr = [0,1];
  for (let i = 1; i < n; i++) {
    fibArr[i + 1] = fibArr[i] + fibArr[i - 1];
  }
  return fibArr[n];
}

console.log(fibFinder(32))

// Leave this so that we can test your code:
module.exports = fibFinder;

To pass all tests, I made a for loop.

approach with for loop
function fibFinder(n) {
  if(n===0) return 0;
  if(n===1) return 1;
  let sum = 0;
  let fib = [0,1];
  for(let i = 1; i < n; i++){
    sum = fib[0] + fib[1];
    fib[0] = fib[1];
    fib[1] = sum
  }
  return sum;
}

Binet’s formula

But due to the system and the relation to the golden ratio, I was wondering if there is a formula to get the nth sum without recursion or looping. And so I found Binet’s formula:


(screenshot from uni-oldenburg.de )

And the derivation of the golden ratio on Wikipedia:

So I transcribed it to JS, leading to this code:

function fibFinder(n) {
  const goldenRatio = (1 + Math.sqrt(5)) / 2;
  const conjugate = (1 - Math.sqrt(5)) / 2;
  const binetsFormula = n => (goldenRatio ** n - conjugate ** n) / Math.sqrt(5);
  return binetsFormula(n);
}

It must be much faster when it comes to bigger numbers and returns the same results – yet just 4/5 tests pass (and a little cheating because I couldn’t have googled Binet’s formula in an interview).

1 Like

Just tossing this out there… All numbers in JS are floats. Are your results turning up as floats? Well, yeah, dumb question. Have you tried massaging an integer from the result:

 return parseInt(binetsFormula(n), 10)
1 Like

Thanks for the input! I just tried your suggestion, but unfortunately it doesn’t have an effect – neither on the visible output of my function calls, nor on the tests. Still just 4/5 passing.

1 Like

Are your results all integers? Are you getting 6765 as the 20th Fib?

Aside

I just completed the challenge using my old favorite approach, destructuring assignment and passed all the tests.

1 Like

No, you’re right. It’s a float and with parseInt applied the return value is 6764 rather than 6765.

Rounding it does the trick:

return Math.round(binetsFormula(n));

Thanks a lot!

How is your solution? Didn’t see it here…

1 Like