This was my go at it.
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.
That is an indefensible statement and could not be farther from the truth.
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.
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.
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;
}
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;
- Recursion will keep a lot of memory in call stack until it release stack after end. More and more with any next step
- 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
- 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;
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).
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)
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.
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.