Last Updated: 5 Feb, 2021

N-th Fibonacci Number

Moderate

Asked in companies

Solve now

Problem statement

You are given an integer ‘N’, your task is to find and return the N’th Fibonacci number using matrix exponentiation.

Since the answer can be very large, return the answer modulo 10^9 +7.

Fibonacci number is calculated using the following formula:

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

For Example:

For ‘N’ = 5, the output will be 5.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the integer for which we have to find its equivalent Fibonacci number.

Output Format:

For each test case, print a single integer representing the N’th Fibonacci number.

Return answer modulo 10^9 + 7.

Output for each test case will be printed in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5

Time Limit: 1 sec.

Follow Up:

Can you solve it in Time Complexity better than O(N)?

Solve now

Approaches

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

Solve now

02 Approach

Ans of ‘i-th’ number is = ‘ans[i-1] + 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]’.

Solve now

03 Approach

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

Solve now

04 Approach

Observe that if we take the ‘N-1’th power of the matrix ‘COEF’ = [ [0, 1], [1, 1] ], then the bottom right element of the resultant matrix i.e ‘RESULT[1][1]’ will give the ‘N’th Fibonacci number.

More details can be found at the given link.

https://cp-algorithms.com/algebra/fibonacci-numbers.html

Algorithm:

multiply function:
1. It will take two matrices as arguments and return the product of these two matrices.
Matrix_power function:
1. It will take a matrix and an integer ‘N’ as arguments and return the ‘N’th power of the matrix.
2. We will declare an identity matrix ‘RES’ of size 2x2.
3. Now while ‘N’ is not equal to 0
  1. If n is odd we will multiply the ‘COEF’ matrix with the ‘RES’.
  2. Then we will multiply the ‘COEF’ matrix with itself and divide ‘N’ by 2.
4. Finally, return the ‘RES’ matrix.
Given function:
1. We will declare the ‘COEF’ matrix.
2. Then we will calculate the ‘N-1’th power of the ‘COEF’ matrix and return the bottom right corner of the resultant matrix.

Solve now