N-th Fibonacci Number

Name: Merge Overlapping Intervals
Brand: LogicMojo
SKU: .
Availability: InStock
Rating: 4.8 (230 reviews)

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: N-th Fibonacci Number
Approach 1: Using Recursion
Approach 2: Using Dynamic Programming
Approach 3: Using Formula

Logicmojo - Updated Dec 12, 2023

Problem Statement: N-th Fibonacci Number

Write a program to calculate the nth Fibonacci number where n is a given positive number.

Every number after the first two is the sum of the two preceding ones, which is known as Fibonacci's sequence.For example, consider the following series:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … and so on.

Given a number n, print n-th Fibonacci Number.

Examples:

Input : n = 5
Output : 5

Input : n = 10
Output : 55

We have presented two approaches to find the n-th fibonacci number:

• Using Recursion
• Using Dynamic Programming
• Using Formula

Approach 1: Using Recursion

The following recurrence relation defines the sequence F_n of Fibonacci numbers:

F{n} = F{n-1} + F{n-2} with base values F(0) = 0 and F(1) = 1.

C++ Implementation:

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

int fib(int n)
{
	if (n <= 1)
		return n;
	return fib(n-1) + fib(n-2);
}

int main ()
{
	int n = 10;
	cout << fib(n);
	getchar();
	return 0;
}

        Try it Yourself

Java Implementation:

class fibonacci
{
	static int fib(int n)
	{
    	if (n <= 1)
	    return n;
	    return fib(n-1) + fib(n-2);
	}
	
	public static void main (String args[])
	{
    	int n = 10;
	    System.out.println(fib(n));
	}
}

        Try it Yourself

Python Implementation:

def fibonacci(n, second_last, last):
	if n-1 == 0:
		return second_last
	else:
		new_last = second_last + last
		second_last = last
		return fibonacci(n-1, second_last, new_last)


if __name__ == "__main__":
	print(fibonacci(10, 0, 1))

        Try it Yourself

Time complexity: O(n), which is a linear

Space complexity:O(n) if we consider the function call stack size, otherwise O(1).

Approach 2: Using Dynamic Programming

We can also improve the time complexity of the recursive approach by saving values that have already been calculated in a data structure like a list. And the function fib() will check if a subproblem is already solved or not. If solved before we will not solve it again.

C++ Implementation:

#include <iostream>
#include <unordered_map>
using namespace std;
 
int fib(int n, auto &lookup)
{
    if (n <= 1) {
        return n;
    }
 
    if (lookup.find(n) == lookup.end()) {
        lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup);
    }
 
    return lookup[n];
}
 
int main()
{
    int n = 8;
    unordered_map<int, int> lookup;
 
    cout << "F(n) = " << fib(n, lookup);
 
    return 0;
}

        Try it Yourself

Java Implementation:

import java.util.HashMap;
import java.util.Map;
 
class Main
{
    public static int fib(int n, Map<Integer, Integer> lookup)
    {
        if (n <= 1) {
            return n;
        }
 
        lookup.putIfAbsent(n, fib(n - 1, lookup) + fib(n - 2, lookup));
 
        return lookup.get(n);
    }
 
    public static void main(String[] args)
    {
        int n = 10;
        Map<Integer, Integer> lookup = new HashMap<>();
 
        System.out.println("F(n) = " + fib(n, lookup));
    }
}

        Try it Yourself

Python Implementation:

def fib(n, lookup):
 
    if n <= 1:
        return n
 
    if n not in lookup:
        lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup)
 
    return lookup[n]
 
 
if __name__ == '__main__':
 
    n = 8
    lookup = {}
 
    print('F(n) =', fib(n, lookup))

        Try it Yourself

Approach 3: Using Formula

In this method we directly implement the formula for nth term in the fibonacci series.

F_n = {[(√5 + 1)/2] ^ n} / √5

C++ Implementation:

#include<iostream>
#include<cmath>

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

int main ()
{
    int n = 10;
    std::cout << fib(n) << std::endl;
    return 0;
}

        Try it Yourself

Java Implementation:

import java.util.*;

class Main{

static int fib(int n) {
    double phi = (1 + Math.sqrt(5)) / 2;
    return (int) Math.round(Math.pow(phi, n)/ Math.sqrt(5));
}

public static void main(String[] args) {
	    int n = 9;
	    System.out.println(fib(n));
	}
}

        Try it Yourself

Python Implementation:

import math

def fibo(n):
	phi = (1 + math.sqrt(5)) / 2

	return round(pow(phi, n) / math.sqrt(5))
	
if __name__ == '__main__':
	
	n = 10
	
	print(fibo(n))

        Try it Yourself

Time Complexity: O(logn), this is because calculating phi^n takes logn time

Space Complexity: O(1)

With this article at Logicmojo, you must have the complete idea of solving Nth Fibonacci Number problem.