Fibonacci numbers

Difficulty Level Easy
Frequently asked in Apple DBOI Google Infosys JP Morgan MAQ o9 solutions SAP Labs
Math SequenceViews 2275

Fibonacci numbers are the numbers that form the series called Fibonacci series and are represented as Fn. The first two Fibonacci numbers are 0 and 1 respectively i.e. F0=0 and F1=1. Starting from the third Fibonacci number each Fibonacci number is the sum of its previous two numbers in the series.

Fn = Fn-1 + Fn-2

The fibonacci series – 0, 1, 1, 2, 3, 5, 8, 13……

Given an integer n. Find the nth Fibonacci number.

Example

Input: n=5

Output: 5

Input: n=9

Output: 34

Recursive Method

Algorithm

  1. Initialise a variable n.
  2. Base case – if n is less than equal to 1 return n.
  3. Recursive case – return fn (n-1) + fn (n-2).

Time Complexity : O(1.6180)n     (1.6180 is also known as the golden ratio)

Space Complexity : O(1)

C++ Program for Fibonacci numbers

#include<bits/stdc++.h> 
using namespace std; 
  
int fn(int n){ 
    if(n<=1) 
        return n; 
    return fn(n-1) + fn(n-2); 
} 
  
int main (){ 
    int n=6; 
    cout<<fn(n); 
    return 0; 
}
Output :
8

Java Program for Fibonacci numbers

class fibNumbers{ 
    static int fn(int n){ 
        if(n<=1) 
           return n; 
        return fn(n-1) + fn(n-2); 
    } 
       
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output : 
8

Recursive tree for the above code

Fibonacci numbers

We can see from the above tree that some functions are being called more than once. 

Dynamic Programming Method

Re-calculations of same functions like above can be avoided using DP.

Algorithm

  1. Initialize a variable n and an array f to store Fibonacci numbers.
  2. Initialize the first two elements of array as 0 and 1 respectively..
  3. Traverse all the values till n starting from 2 one by one and update the array values as the sum of the previous two elements in array.
  4. Return f[n].

Time Complexity: O(n)     

Space Complexity: O(n)

C++ Program for Fibonacci numbers

#include<bits/stdc++.h>
using namespace std;

int fn(int n){ 
  int f[n+2];
  
  f[0] = 0; 
  f[1] = 1; 
  
  for(int i=2; i<=n; i++){ 
      f[i] = f[i-1] + f[i-2]; 
  } 
  
  return f[n]; 
} 
  
int main (){ 
  int n = 6; 
  cout<<fn(n);
  return 0; 
}
Output : 
8

Java Program for Fibonacci numbers

class fibNumbers{ 
    static int fn(int n){ 
        int[] f = new int[n+2]; 
        
        f[0] = 0; 
        f[1] = 1; 
        
        for(int i=2; i<=n; i++){ 
            f[i] = f[i-1] + f[i-2]; 
        } 
        
        return f[n]; 
    } 
    
  
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output : 
8

More space-optimized Method

Algorithm

  1. Initialise three variable x=0, y=1, z.
  2. Traverse all the values till n starting from 2 one by one and update z as the sum of x and y, x=y, and y=z.
  3. Return y.

Time Complexity: O(n)     

Space Complexity: O(1)

C++ Program for Fibonacci numbers

#include<bits/stdc++.h>
using namespace std;

int fn(int n){ 
    int x=0, y=1, z;
    
    for(int i=2; i<=n; i++){ 
        z = x + y;
        x = y;
        y = z;
    } 
    
    return y; 
} 

int main (){ 
    int n = 6; 
    cout<<fn(n);
    return 0; 
}
Output :
8

Java Program for Fibonacci numbers

class fibNumbers{ 
    static int fn(int n){ 
        int x=0, y=1, z; 
        if(n == 0) 
            return x; 
        for(int i=2; i<=n; i++){ 
            z = x + y; 
            x = y; 
            y = z; 
        } 
        return y; 
    } 
  
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output :
8

Using Direct Formula

Here we’ll directly use the formula to find the nth Fibonacci number i.e.

Fn = ( ( ( (5 + 1) / 2) ^ n) / 5)

Time Complexity : O(1)     

Space Complexity : O(1)

C++ Program

#include<bits/stdc++.h>
using namespace std;

int fn(int n){ 
    double gr = (1 + sqrt(5)) / 2; 
    return round(pow(gr, n) / sqrt(5)); 
} 

int main (){ 
    int n = 6; 
    cout<<fn(n);
    return 0; 
}
Output :
8

Java Program

import java.util.*;

class fibNumbers{ 
    static int fn(int n){ 
        double gr = (1 + Math.sqrt(5)) / 2; 
        return (int) Math.round(Math.pow(gr, n) / Math.sqrt(5));
    } 
    
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output :
8

Reference

Interview Questions

Translate »