Last Updated: 29 Jun, 2021
Find the N-th term
Hard
Asked in companies
You want to get tutelage under the Ultimate Ninja Ankush, but for that you have to pass his test. His test is simple: he has given you a relation function, F(n) = 2*F(n-1) + 3*F(n-2),where F(0) = F(1) = 1 and wants you to find the ‘N’th term for the function.
The 'N'th term can be very large, return it after modulus 10^9 + 7.
For example:
Given ‘N’ = 3,
F(3) = 13,This is because F(0) = 1, F(1) = 1, Therefore F(2) = 2*F(1) + 3*F(1), therefore F(2) = 5, and F(3) = 2*F(2) + 3*F(1), therefore F(3) = 13.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines contains a single integer ‘N’, which denotes the number given to us.
Output Format :
For each test case, You are supposed to return the Nth term for the given relation.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10 ^ 9
Time Limit: 1sec.
Approaches
The idea is to recur according to the given relation i.e. F(N) = 2*F(N - 1) + 3*F(N - 2).
The steps are as follows:
- The base condition would be if ‘N’ is 0 or 1, then return 1.
- Else recur for ‘2 * nthTerm(N - 1)’ + ‘3 * nthTerm(N - 2)’.
The idea is to maintain a ‘dp’ array where ‘dp[i]’ represents the ‘I’th term for the given relation, where ‘dp[i]’ = ‘2 * dp[i-1]’ + ‘3 * dp[i-2]’.
The steps are as follows:
- Maintain a ‘dp’ array, where ‘dp[i]’ represents the ‘i’th term.
- Assign ‘dp[0]’, and ‘dp[1]’ as 1, since it is the base condition.
- Loop from 2 to ‘N’ using ‘i’:
- ‘dp[i]’ = ‘2 * dp[i-1]’ + ‘3 * dp[i-2]’.
- Return dp[n] as the final result.
The idea is to use Matrix Exponentiation to speed up the function computation.
All such problems where a term is a function of other terms in a linear fashion. Then these can be solved using the Matrix . First, we make a transformation matrix and then just use matrix exponentiation to find the Nth term. This can be done logarithmic time instead of linear time as seen in the first approach.
For matrix exponentiation we need:
- ‘N’: Where ‘N’ represents the term we want to find.
- ‘Initial-values’: Basically F(0) and F(1).
- Transformation-Matrix: Which helps us finding F[N], since F(‘N’) = ‘TM’ * ‘initial-values’, where ‘TM’ represents the Transformation-Matrix.
We further multiply the Matrix ‘N’ times and do this in logarithmic time by following the logic:
- ‘A ^ N’ = ‘A’ * ‘ A ^ (N/2)*2 ’ [If ‘N’ is odd]
- ‘A ^ N’ = ‘ A ^ (N/2)*2 ’ [If ‘N’ is even]
In the solution, we are using a similar idea.
The steps are as follows:
- Maintain a 2-D matrix ‘res’ which is the identity matrix of size - 2, i.e. {{1,0}, {0,1}}.
- Maintain a 2-D matrix ‘tMat’ which is the transformation matrix {{2,3}, {1,0}}.
- Now we have to multiply the ‘tMat’ matrix ‘N’ times, this can be done in logarithmic form as described above.
- Finally return ‘res[0][0] * res[0][1]’ % mod, as the final result, where ‘mod’ is 1e9 + 7, this is because the answer can be represented as [F(n) / (F(n-1)] = ‘tMat ^ ‘N - 1’’ * [res[0][0] / res[1][0]].