Sourav Dey
Sourav's Digital πŸ“˜ Notebook

Sourav's Digital πŸ“˜ Notebook

LeetCode Question - 509. Fibonacci Number πŸ€ͺ

LeetCode Question - 509. Fibonacci Number πŸ€ͺ

6th July 2022 | πŸ—“ Daily LeetCode Challenge - #6

Sourav Dey's photo
Sourav Dey
Β·Jul 7, 2022Β·

4 min read

Subscribe to my newsletter and never miss my upcoming articles

Play this article

About the Series

Problem-solving is a key skill set for any tech-related stuff you might be working on.

When it comes to developers it's one of the most crucial skills which is needed in almost any day-to-day code you might be writing.

So, this series of blogs is all about practicing Daily LeetCode Challenges & Problem-solving. πŸš€

Problem Statement

Fibonacci Number

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.

Video Explanation

Sketch-annotation-element-stroke-line-arrow-spiral-up.png

Solution 1: Recursive Approach

Algorithm

  1. This is the recursive solution where If n is 0 it will return 0 or if n is 1 it will return 1. This is the base case for recursion
  2. Recursively call the f(n-1) and f(n-2) to return the final value of f(n)
  3. Finally we get out f(n).

Code in JS πŸ§‘β€πŸ’»

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

Time Complexity : O(n)

Space Complexity: O(n)

Solution 2: Iterative approach with an array

Algorithm

  1. First of all, n = 0 return 0 and for n = 1 return 1
  2. Create an array and store the first two values of the Fibonacci sequence in the array
  3. Now update the ith value of the array with the i-1 value + the i-2 value of the array.
  4. Repeat the same for n iterations and then the array will have the nth value too.
  5. Return the nth value from the array

Code in JS πŸ§‘β€πŸ’»

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n < 2) return n;
  var fibArray = [];
  fibArray[0] = 0;
  fibArray[1] = 1;
  for (var i = 2; i <= n; i++) {
    fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
  }
  return fibArray[n];
};

Time Complexity : O(n)

Space Complexity: O(n)

Solution 3: Iterative approach without an array

Algorithm

The approach is similar to the 2nd solution but it is done without using a new array.

  1. First of all, n = 0 return 0 and for n = 1 return 1
  2. Store the last two values of the Fibonacci series in f1 and f2.
  3. Update f1 with f2
  4. Update f2 with the current sum of f1 and f2.
  5. Steps 2 and 3 will be repeated till we get the final value after n iterations.
  6. Return f2.

Code in JS πŸ§‘β€πŸ’»

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n < 2) return n;
  var f1 = 0;
  var f2 = 1;
  for (var i = 2; i <=n; i++) {
    var currentSum = f1 + f2;
    f1 = f2;
    f2 = currentSum;
  }
  return f2;
};

Time Complexity : O(n)

Space Complexity: O(1)

Similar Questions for practice

Now it is time to try some similar questions

You can find me on the web 🌍

Add your solution or approach in the comments below. Also, show your love by Sharing the blog. πŸ€—

β€œBelief creates the actual fact.”

~ William James

Did you find this article valuable?

Support Sourav Dey by becoming a sponsor. Any amount is appreciated!

See recent sponsors |Β Learn more about Hashnode Sponsors
Β 
Share this