LeetCode #509: Fibonacci Number

LeetCode Question - 509. Fibonacci Number 🤪

About the Series

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

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

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

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

Video Explanation

Solution 1: Recursive Approach

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

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

Solution 2: Iterative approach with an array

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

/**
 * @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];
};

Solution 3: Iterative approach without an 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.

/**
 * @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;
};

Similar Questions for practice

• Climbing Stairs
• Split Array into Fibonacci Sequence
• Length of Longest Fibonacci Subsequence
• N-th Tribonacci Number

You can find me on the web 🌍

• Github
• LinkedIn
• Twitter

“Belief creates the actual fact.”

~ William James