N-th Fibonacci Number
Last Updated: 5 Feb, 2021
Difficulty: Moderate
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)?
Approach 1
Approach 2
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]’.
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'.
Approach 4
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:
- It will take two matrices as arguments and return the product of these two matrices.
- Matrix_power function:
- It will take a matrix and an integer ‘N’ as arguments and return the ‘N’th power of the matrix.
- We will declare an identity matrix ‘RES’ of size 2x2.
- Now while ‘N’ is not equal to 0
- If n is odd we will multiply the ‘COEF’ matrix with the ‘RES’.
- Then we will multiply the ‘COEF’ matrix with itself and divide ‘N’ by 2.
- Finally, return the ‘RES’ matrix.
- Given function:
- We will declare the ‘COEF’ matrix.
- Then we will calculate the ‘N-1’th power of the ‘COEF’ matrix and return the bottom right corner of the resultant matrix.
