Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 23 Oct, 2020

Easy

```
The series is 1-based indexed.
```

```
The first line contains an integer T denoting the number of test cases. Then each test case follows.
The first line of each test case contains three space-separated integers ‘X’, 'Y', and ‘N’, respectively where ‘X’ and ‘Y’ represent the first and second element of the series while N represents which number of the sequence we have to find out.
```

```
For each test case, print a single line containing a single integer denoting the Nth number of the series.
The output of each test case will be printed in separate lines.
```

```
You are not required to print the expected output; it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= N <= 10 ^ 18
-10 ^ 6 <= X, Y <= 10 ^ 6
Time limit: 1 sec.
```

Let’s define a **dp** array of size N, where dp[i] represents the i-th Fibonacci number. For each block, let’s compute the answer in a top-down fashion, starting with the leftmost blocks (dp[0] and dp[1]). We will iterate through the array for** i = 2 to N **and then we can fill the array in a top-down manner like:

Since, during this method, we only need the previous two states, we can store the last two states in two variables instead of using a whole array.

**Here is the algorithm:**

**Initialise variable****sum = 0**that stores the sum of the previous two values.**Now, run a loop from****i = 2 to N-1**and for each index update value of**sum = X + Y**and**X = Y, Y = sum**.**Finally, return the****sum**, which is the required**Nth element**.

The N’th term of a Fibonacci series can be computed using matrix multiplication as terms of the Fibonacci series follows the following relation.

(Fn-1 Fn) = ( Fn−2 Fn−1 ) ⋅ ( 0 1 )

1 1

If we extend this further, we have:

(Fn Fn+1) = ( F0 F1 ) ⋅ (P)^{N}

Where P is ( 0 1 )

1 1 .

As in the relation, rank is zero-based, so we will compute the answer for n = n-1.

We will find Fn corresponding to the n’th element of the Fibonacci Series and X will be F0 and Y will be F1.

We will find the P^{N} using Binary exponentiation using takes O(logN) time.

- Defining MATRIX_MULTI(‘A’, ‘B’) which returns the matrix product of ‘A’,’B’.
- Set ‘R’ as the length of ‘A’ matrix.
- Set ‘C’ as the length of ‘B[0]’.
- Declare a ‘RESULT’ matrix of size R*C.
- Set all values of ‘RESULT’ to 0.
- For i in range 0 to ‘R’ -1 :
- For j in range 0 to ‘C’-1:
- For k in range 0 to the length of ‘B’-1:
- Set ‘RESULT[i][j]’ = ( ‘RESULT[i][j]’ + ( A[i][k] * B[k][j]) %(10^9 +7) )%(10^9 +7).

- For k in range 0 to the length of ‘B’-1:

- For j in range 0 to ‘C’-1:
- Return ‘RESULT’ matrix.

- Defining BINARY_EXPO(‘A’,’N’) which returns the matrix A
^{N}.- If N ==0:
- Return Unitt matrix of size 2.

- If N == 1:
- Return ‘A’.

- If N is odd:
- Return MATRIX_MULTIPLY(‘A’,BINARY_EXPO(‘A’,’N’-1)).

- If N is even:
- Set ‘TEMP’ as BINARY_EXPO(‘A’, ’N’/2).
- Return MATRIX_MULTIPLY(‘TEMP’,’ TEMP’).

- If N ==0:
- Set ‘N’ to ‘N’-1.
- Declare a matrix ‘P’ of size 2*2.
- Set ‘P’ as [ [0,1],[1,1] ].
- Set ‘PN’ as BINARY_EXPO(‘P’,’N’).
- Set ‘M’ as [ [‘X’, ‘Y’] ] corresponding to the matrix having ‘X’ and ‘Y’.
- Set ‘ANS’ as the product of matrix ‘M’ and matrix ‘PN’.
- Set ‘ANS’ as MATRIX_MULTIPLY(‘M’, ‘PN’).
- Return ‘ANS[0][0]’ corresponding to the value of Fn.