Find the N-th term

Posted: 29 Jun, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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) = 2F(n-1) + 3F(n-2),where F(0) = F(1) = 1 and wants you to find the ‘N’th term for the function.

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.
Approach 1

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