# Nth Fibonacci

Decode the famous Fibonacci sequence and learn how to efficiently compute its Nth number with algorithmic finesse.

Recursion
easy

Published At

6/4/2021

The Fibonacci sequence is defined as follows: the first number of the sequence isĀ 0, the second number isĀ 1, and the nth number is the sum of the (n - 1)th and (n - 2)th numbers. Write a function that takes in an integerĀ nĀ and returns the nth Fibonacci number.

Important note: the Fibonacci sequence is often defined with its first two numbers asĀ F0 = 0Ā andĀ F1 = 1. For the purpose of this question, the first Fibonacci number isĀ F0; therefore,Ā getNthFib(1)Ā is equal toĀ F0,Ā getNthFib(2)Ā is equal toĀ F1, etc..

### Sample Input #1

js
``n = 2``
js
``n = 2``

### Sample Output #1

js
``1 // 0, 1``
js
``1 // 0, 1``

### Sample Input #2

js
``n = 6``
js
``n = 6``

### Sample Output #2

js
``5 // 0, 1, 1, 2, 3, 5``
js
``5 // 0, 1, 1, 2, 3, 5``

### Hints

Hint 1

The formula to generate the nth Fibonacci number can be written as follows: F(n) = F(n - 1) + F(n - 2). Think of the case(s) for which this formula doesn't apply (the base case(s)) and try to implement a simple recursive algorithm to find the nth Fibonacci number with this formula.

Hint 2

What are the runtime implications of solving this problem as is described in Hint #1? Can you use memoization (caching) to improve the performance of your algorithm?

Hint 3

Realize that to calculate any single Fibonacci number you only need to have the two previous Fibonacci numbers. Knowing this, can you implement an iterative algorithm to solve this question, storing only the last two Fibonacci numbers at any given time?

Optimal Space & Time Complexity

O(n) time | O(1) space - where n is the input number

Solution-1
js
``````function getNthFib(n) {
let fib = [];
for (let i = 0; i < n; i++) {
if (i <= 1) {
fib.push(i)
continue;
}
fib.push(fib[i - 1] + fib[i - 2]);
}
return fib.pop()
}

// 0, 1, 1, 2, 3, 5, 8, 13
// 2 (n-1) + (n-2) = 1 + 0
// 6 (6-1) + (6-2) = 5 + 4 = 9``````
Solution-1
js
``````function getNthFib(n) {
let fib = [];
for (let i = 0; i < n; i++) {
if (i <= 1) {
fib.push(i)
continue;
}
fib.push(fib[i - 1] + fib[i - 2]);
}
return fib.pop()
}

// 0, 1, 1, 2, 3, 5, 8, 13
// 2 (n-1) + (n-2) = 1 + 0
// 6 (6-1) + (6-2) = 5 + 4 = 9``````
Solution-2
js
``````function getNthFib(n) {
if (n === 1) return 0;
if (n === 2) return 1;
return getNthFib(n - 1) + getNthFib(n - 2);
}``````
Solution-2
js
``````function getNthFib(n) {
if (n === 1) return 0;
if (n === 2) return 1;
return getNthFib(n - 1) + getNthFib(n - 2);
}``````

š¦Ø

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek š

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.