Fibonacci Number LeetCode Solution

Table of Contents

Problem Statement:

Fibonacci Number LeetCode Solution says 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).

Example 1:

Input:

 n = 2

Output:

Explanation:

 F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input:

 n = 3

Output:

Explanation:

 F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input:

 n = 4

Output:

Explanation:

 F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

0 <= n <= 30

ALGORITHM –

The Fibonacci numbers are the numbers in the following integer sequence:

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ……$. We can see the Fibonacci series sequences in the natural world like the sunflower, the nautilus, and the galaxy.

In mathematical terms, the sequence F(n) of Fibonacci numbers is defined by the recurrence relation

F(n)=F(n−1)+F(n−2)

with seed values F(0)=0 and F(1)=1.

The Fibonacci sequence is often used in introductory computer science courses to explain recurrence relations, dynamic programming, and proofs by induction.

IDEA –

In order to find Fibonacci Number LeetCode Solution. We will use the concept of Fibonacci. So Fibonacci series generates the subsequent number by adding two previous numbers. The Fibonacci series starts from two numbers − F₀ & F₁. The initial values of F₀ & F₁ can be taken 0, 1, or 1, 1
Fn = Fn-1 + Fn-2

For example,

F5 = 0,1, 1, 2, 3

Image –

Fibonacci Number LeetCode Solution

class Solution:
    def fib(self, n: int) -> int:
        if n == 0 or n == 1:
            return n
        
        a = 0
        b = 1
        for i in range(1,n):
            c = a+b
            a = b
            b = c
            
        return b

class Solution 
{
    public int fib(int N)
    {
        if(N <= 1)
            return N;
        
    int a = 0, b = 1;
    
    while(N-- > 1)
    {
      int c = a + b;
      a = b;
      b = c;
    }
        return b;
    }
}

Time Complexity – O(N), As we have traversed only one time.

Space Complexity – O(1), As we haven’t taken any extra space.