# JSDevLife

JavaScript Solutions, Competitive programming in JavaScript, MCQ in JS

# A Solution to Leetcode problem 509. Fibonacci Number in JavaScript

## Introduction:

The Fibonacci numbers are a series of numbers in which each number is the sum of the previous two numbers. The first two numbers in the series are usually defined as 0 and 1, and the subsequent numbers are calculated by adding the previous two numbers. For example, the Fibonacci sequence starting with 0 and 1 is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. In this post, we will be discussing a solution to the LeetCode problem #509: Fibonacci Number, using JavaScript.

## Problem statement:

The Fibonacci numbers, commonly denoted `F(n)` form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from `0` and `1`. That is,

```F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
```

Given `n`, calculate `F(n)`.

Example 1:

```Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
```

Example 2:

```Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
```

Example 3:

```Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
```

Constraints:

• ```0 <= n <= 30 ```

## Solution:

One way to solve this problem is to use a recursive approach, where we can define a function fib that returns the Fibonacci number for a given input n. The function will be called recursively with n-1 and n-2 as inputs until we reach the base case of n = 0 or n = 1, at which point we return 0 or 1 respectively.

Here is the implementation of this solution in JavaScript:

/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
let arr =[];
if(n<2){
return n;
}else{
return fib(n-1)+fib(n-2)
}
};

This solution has a time complexity of O(2^n) as we are making two recursive calls for each function call. The space complexity is also O(n) as the maximum depth of the recursive call stack is n.

A better solution would be to use an iterative approach, where we can use a loop to calculate the Fibonacci numbers and store them in an array. This way, we can avoid the recursive calls and achieve a time complexity of O(n).

Here is the implementation of this solution in JavaScript:

``````const fib = function(n) {
let fibArr = [0, 1];
for (let i = 2; i <= n; i++) {
fibArr[i] = fibArr[i-1] + fibArr[i-2];
}
return fibArr[n];
};``````

We first create an array fibArr with the first two Fibonacci numbers (0 and 1). Then, we use a loop to iteratively calculate and store the subsequent Fibonacci numbers in the array. Finally, we return the nth element of the array as the result.

This solution has a time complexity of O(n) and a space complexity of O(n) as we are using an array to store the Fibonacci numbers.

## Conclusion:

In this post, we discussed two solutions to the LeetCode problem #509: Fibonacci Number, using JavaScript. The first solution used a recursive approach with a time complexity of O(2^n) but second solution has a time complexity of o(n).