Find the N-th term

Hard
0/120
Average time to solve is 50m
profile
Contributed by
12 upvotes
Asked in companies
DirectiCodenationBirdEye

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1 :

2
3
4

Sample Output 1 :

13
41

Explanation of the Sample Input 1:

In the first test case,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.

In the second test case, F(4) = 41, This is because F(2) = 5, F(3) = 13, F(4) = 2*F(3) + 3*F(2), therefore F(4) = 41.

Sample Input 2 :

2
5
2

Sample Output 2 :

121
5
Hint

Can this be found recursively?

Approaches (3)
Recursion

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

O(2 ^ N), Where ‘N’ is the number given to us.


 

Since we are recurring 2 times for each ‘N’, the overall time complexity will be O(2 ^ N).

Space Complexity

O(N), Where ‘N’ is the number given to us.


 

Since we are recurring 2 times for each ‘N’,  therefore, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Find the N-th term
Full screen
Console