The Fibonacci Number algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.


The question for an algorithm is,


The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1

F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).


Example 1:

Input: n = 2

Output: 1

Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.


Example 2:

Input: n = 3

Output: 2

Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.



Example 3:

Input: n = 4

Output: 3

Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.


Let's start with the algorithm,


var fib = function(n) {

    if(n<1)

    {

      return 1;

    }

    let curSeq=1;

    let prevSeq=0;

    let temp=0;

    

    for(let i=1;i<n;i++)

    {

        temp=curSeq;

        curSeq=prevSeq+curSeq;

        prevSeq=temp;

    }

    return curSeq;

};



I hope you understood the algorithm. If you have any doubts, please let us know in the comments.