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

Input: n=5

Output: 5

Input: n=9

Output: 34

## 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

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

## 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  Smallest Multiple of a Given Number

Interview Questions

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions