Nth Element Of Modified Fibonacci Series
You have been given two integers ‘X’ and ‘Y’ which are the first two integers of a series and an integer ‘N’. You have to find the Nth number of the series using the Fibonacci rule given by f(x) = f(x - 1) + f(x - 2).

The answer may be very large, return it after modulus 10 ^ 9 + 7.

Note:

The series is 1-based indexed.

Input Format:

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.

Output Format:

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.

Note

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

Constraints:

1

Question

Nth Element Of Modified Fibonacci Series

You have been given two integers ‘X’ and ‘Y’ which are the first two integers of a series and an integer ‘N’. You have to find the Nth number of the series using the Fibonacci rule given by f(x) = f(x - 1) + f(x - 2).

The answer may be very large, return it after modulus 10 ^ 9 + 7.

Note:

The series is 1-based indexed.

Input Format:

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.

Output Format:

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.

Note

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

Constraints:

1 <= T <= 100
1 <= N <= 10 ^ 18
-10 ^ 6 <= X, Y <= 10 ^ 6

Time limit: 1 sec.

Accepted Answer

Dynamic Programming

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:

dp[i] = dp[i-1] + dp[i-2].

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.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, only a constant extra space is required.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ represents which number of the sequence we have to find out.

As we are iterating over the whole array only once so the time complexity will be O(N).

Accepted Answer

Matrix Multiplication.

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.

Algorithm:

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

Space Complexity: O(logn)Explanation:

O( log(N) ), where ‘N’ represents which number of the sequence we have to find out.

In this approach, we are using recursion to find P^N using binary exponentiation. So it takes logN space in stack memory. Hence, the overall space complexity is O( log(N)).

Time Complexity: O(logn)Explanation:

O( log(N)), where ‘N’ represents which number of the sequence we have to find out.

In this approach, we are just doing matrix multiplication of constant size matrix which takes constant time, and using binary exponentiation to find P^N which takes log(N) time. Hence, the overall time complexity is O( log(N) ).