Last Updated: 23 Oct, 2020

# Nth Element Of Modified Fibonacci Series

Easy

## Problem statement

#### 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.
``````

## Approaches

### 01 Approach

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:

1. Initialise variable sum = 0 that stores the sum of the previous two values.
2. 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.
3. Finally, return the sum, which is the required Nth element.