Home » Technical Interview Questions » Algorithm Interview Questions » Fibonacci numbers

Fibonacci numbers


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. F=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

READ  Special Number

Interview Questions

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup