Nth Fibonacci Number

PROBLEM STATEMENT

    F(n) = F(n-1) + F(n-2), 
    Where, F(1) = F(2) = 1

The first line of each test case contains a real number ‘N’.

For each test case, return its equivalent Fibonacci number.

1 <= N <= 10000     
Where ‘N’ represents the number for which we have to find its equivalent Fibonacci number.

Time Limit: 1 second

Approach 1

In this approach, we use recursion and uses a basic condition that :
- If ‘N’ is smaller than ‘1’(N<=1) we return ‘N’
- Else we call the function again as ninjaJasoos(N-1) + ninjaJasoos(N-2).
In this way, we reached our answer.

Approach 2

Ans of ‘i-th’ number is = ‘ans[i-11+ans[i-2]’, so

With the help of dynamic programming, we try to store the previous value as the previous value leads to a solution.
So we use an array named as ‘dp’ of size ‘N+1’ to store the value.
On the first index of ‘dp[0]=0’ we store ‘0’ and on the first index of ‘dp[1]=1’ we store ‘1’.
Now run a loop and iterate through the “Nth”number like ‘dp[i]=dp[i-2]+dp[i-1]’.
dp[n] will contain the Fibonacci number of “Nth”number.
Return ‘dp[n]’.

Approach 3

We take three integers a, b, c and we initialized a=0, b=1 as now we want to optimize the space by only storing “2” last numbers as we need only them.
Now we run a loop up to our “Nth” number and by using property the next number is the sum of two previous numbers like “c=a+b.
Now we update “a=b” and “b=c” at every step of the iteration.
In this way when our loop finished “b” contains the “Nth” Fibonacci number.
Return ‘b'.