Nth Fibonacci Number
Nth term of Fibonacci series F(n), where F(n) is a function, is calculated using the following formula -

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

Provided N you have to find out the Nth Fibonacci Number.

Input Format :

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

Output Format :

For each test case, return its equivalent Fibonacci number.

Constraints:

1

Question

Nth Fibonacci Number

    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

Accepted Answer

Recursive Approach

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the given number.

As recursion uses a stack of size ‘N’

Time Complexity: O(2^n)Explanation:

O(2^N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As our function will be called exponentially.

Accepted Answer

Dynamic Programming

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]’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As we are using an array (dp) of size ‘N’ for storing values.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As our loop will run for ‘N’ times.

Accepted Answer

Optimized Dynamic programming

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'.

Space Complexity: O(1)Explanation:

O(1), we are using constant space.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As our loop will run for ‘N’ times.

Top Cognizant Program Analyst interview questions & answers