# N-th Fibonacci Number

Posted: 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.

SIMILAR PROBLEMS

# Subsequence Game

Posted: 14 Jul, 2022

Difficulty: Moderate

# Find all Divisors of a natural number

Posted: 15 Jul, 2022

Difficulty: Easy

# Paint the Stairs

Posted: 15 Jul, 2022

Difficulty: Moderate

# Mohan and Magic Boots

Posted: 16 Jul, 2022

Difficulty: Moderate

# Merge Strings

Posted: 17 Jul, 2022

Difficulty: Moderate