JavaScript Solutions, Competitive programming in JavaScript, MCQ in JS

Sunday, 18 December 2022

Solution to Leetcode problem 509. Fibonacci Number in JavaScript

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





No comments:

Post a Comment