Coding Problem: Nth Fibonacci

Given a number n, find the Fibonacci series up to the n term.

Nov 8, 2021 - 11:11 Updated: Nov 8, 2021 - 11:39

0 77

In this post, we will write a program for calculating Nth Fibonacci.

Problem Statement:

The Fibonacci sequence is defined as follows: the first number of the sequence is 0, the second number is 1, and the nth number is the sum of the (n -1)th and (n - 2)th numbers. Write a function that takes in an integer n and returns the nth Fibonacci number.

Sample Input:

n = 2

Sample Output:

1 // 0, 1

Sample Input:

n = 6

Sample Output:

5 // 0 ,1, 1, 2, 3, 5

Solution:

Method 1: Iterative Solution

To calculate any single Fibonacci number we only need to have the two previous Fibonacci numbers. Knowing this, we can implement an iterative algorithm storing only the last two Fibonacci numbers at any given time.

Time Complexity: O(n)

Space Complexity: O(1)

public class NthFibonacci {
    
    public static int getNthFibonacciNumber(int n) {
       int[] lastTwo = {0 , 1};
       int counter = 3;
       while (counter <= n) {
           int nextFib = lastTwo[0] + lastTwo[1];
           lastTwo[0] = lastTwo[1];
           lastTwo[1] = nextFib;
           counter++;
       }
       return n > 1 ? lastTwo[1] : lastTwo[0];
    }

}

Method 2: Recursion

The formula to generate the nth Fibonacci number can be written as follows: F(n) = F(n - 1) + F(n - 2). We need to implement a simple recursive algorithm. We will make use of memoization to avoid duplicate calcuations.

Time Complexity: O(n)
Auxiliary Space: O(n)

public class NthFibonacci {

    public static int getNthFibonacci(int n) {
        Map<Integer, Integer> memoize = new HashMap<>();
        memoize.put(1, 0);
        memoize.put(2, 1);
        return getNthFibonacci(n, memoize);
    }

    private static int getNthFibonacci(int n, Map<Integer, Integer> memoize) {
        if (!memoize.containsKey(n)) {
            memoize.put(n, getNthFibonacci(n - 1, memoize) + getNthFibonacci(n - 2, memoize));
        }
        return memoize.get(n);
    }

}