Nth Fibonacci | Competitive Programming | Typescript

What is fibonacci series?

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ..

Photo by Yousef Espanioly on Unsplash

You can see fibonacci series in nature.

• Buttercups have 5 petals.
• Lilies and Iris have 3 petals.
• Some delphiniums have 8.
• Corn Marigolds have 13 petals.
• Some asters have 21.
• Daisies can be found with 34, 55 or even 89 petals.

Fibonacci series starts with 0, 1 and subsequent numbers can be formed by adding previous 2 numbers in the series.

F(1) = 0
F(2) = 1
F(3) = F(2) + F(1) = 1 + 0 = 1
F(4) = F(3) + F(2) = 1 + 1 = 2
F(5) = 3
...

We all have solved the fibonacci series in one way or other. But here we are focusing on the interview point of view.

Here is the solution using recursion.

# Solution:1 [O(2^n) Time | O(n) Space]

function getNthFib(n: number): number {
  if(n==1) return 0;
  if(n==2) return 1;
  
  return getNthFib(n-1) + getNthFib(n-2);
}

Such a small and concise code. How cool is that? Not really though! This code tends to perform same computation multiple times, which is not so efficient. Hence we need some cache to store the computed results.

# Solution:2 [O(n) Time | O(n) Space]

interface cache {
  [key: number]: number;
}
function getNthFib(n: number, memo: cache = {1: 0, 2: 1}) {
  if(n in memo){
    return memo[n];
  }
  memo[n] = getNthFib(n-2, memo) + getNthFib(n-1, memo);
  return memo[n];
}

Because this code uses recursion, recursion uses stack memory. It will cause ‘stack overflow’ problem when computing Fibonacci for big N’s.

What is the alternative for this approach?

# Solution:3 [O(n) Time | O(1) Space]

function getNthFib(n: number) {
  let lastTwo = [0, 1];
  let idx = 3;
  while(idx <= n) {
    let result = lastTwo[0] + lastTwo[1];
    lastTwo[0] = lastTwo[1];
    lastTwo[1] = result;
    idx++;
  }
  if(n==1) return lastTwo[0];
  return lastTwo[1];
}