Fibonacci Number LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg eBay Facebook Goldman Sachs Google Infosys JPMorgan Mathworks Microsoft Nvidia Oracle SAP Uber VMware Zillow
ZoomViews 4659

Problem Statement

Fibonacci Number LeetCode Solution – “Fibonacci Number” states that 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).

Fibonacci Number LeetCode Solution

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.

Approach

Idea:

The main observation is that each F(i) is depending on the sum of F(i-1) and F(i-2). Thus we can take two variables that will store the initial value, then we will iterate till N to get the result.

explanation

  • N==0: return 0
  • N==1: return 1
  • default: return fib(N-1) + fib(N-2)

let’s talk about the second approach:

Considering the sequence of [34,55,89] we can see a pattern that is if we divide any two consecutive terms, the division results in an identical number close to 1.618 called the golden ratio. Indeed we have the formula to do this! called Binet’s formula.

Okay? how can we use this golden something! 34 is the 9th term, If we find the pow(golden,Nth term)/sqrt(5) enclosed with a round function, we would get the Nth term value in O(1) time & space!

Code

C++ Code of Fibonacci Number

class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c;
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
};

JAVA Program of Fibonacci Number

class Solution {
    public int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c=0;
        
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
}

Complexity Analysis for Fibonacci Number LeetCode Solution

Time Complexity

O(N)

Space Complexity

O(1)

Translate »