# 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:

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).