Get the nth Fibonacci Number

Given the index n, find nth Fibonacci number.

To begin with, let’s first take a quick look at what Fibonacci series is.

The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
The first two numbers are 0 and 1. And then the next number is always the sum of previous two. 0+1 is equal to 1. 1 + 1 is equal to 2. 1 + 2 is equal to 3. And so on.

The first solution that comes to mind is to use recursion.
The solution will look something like this:

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

The algorithmic run time complexity here is O(2^n) and space complexity is O(n).
The exponential run time complexity is really bad.

So the next question from the interviewer will be how you can do it better.

So if you look at the algorithm closely, there is a lot of repeated work.

                       fib(5)  

                     /                \

               fib(4)                fib(3)  

             /        \              /       \

         fib(3)      fib(2)         fib(2)   fib(1)

        /    \       /    \        /      \

  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)

  /     \

fib(1) fib(0)

For e.g. Fib(2) is computed 3 times. If we can somehow store it once it’s calculated the first time, we can reuse it when needed and this way don’t have to recompute it. We can use any data structure like array or HashTable to store those results. This technique is called memorization. Here is the implementation using hashtable.

Int GetFibonacci(int n)
{
  var dict = new Dictionary();
  dict.Add(0, 0);
  dict.Add(1, 1);
  for(int x=2; x< n+1; x++)
  {
    dict.Add(x, dict[x-1] + dict[x-2])
  }
  return dict[n]
}

So this one has much better time complexity but now uses an extra data structure. Time complexity is O(n) and space complexity is also O(n).

So now again the next question will be can we do better? Let’s see. One more thing to look at is we are storing all the results that we computed so far. Do we need to keep all of them? Or we can only keep last two and get rid of others?
This is how the algorithm will look like for space optimized solution.

int GetFibonacci(int n)

{

  If(n < = 1)

    return n;

  int prevprev = 0;

  int prev = 1

  int current = prevprev + prev;

  for(int x= 2; x<n; x++)

  {

    prevprev = prev;

    prev= current;

    current = prevprev + prev;

  }

  return current;

}

Here the time complexity is O(n) and space complexity is O(1).

Here is the GitHub Link with the working solution. I will recommend you to try it on your own before looking at the solution.

Hope you like this interview question. I will be adding more such questions to my YouTube channel. So please do not forget to subscribe.
Until next time, happy coding 😊