N-th Term Of GP
You are given the first term (A), the common ratio (R) and an integer N. Your task is to find the Nth term of the GP series.

The general form of a GP(Geometric Progression) series is A, A(R), A(R^2), A*(R^3) and so on where A is the first term of GP series

Note :

As the answer can be large enough, return the answer modulo 10^9 + 7.

Input format :

The first line of input contains an integer T denoting the number of queries or test cases. The first line of every test case contains three single space-separated integers N, A, and R denoting the term of GP series required, the first term, and the common ratio respectively.

Output format :

For each test case, print an integer denoting the Nth term of GP in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

N-th Term Of GP

You are given the first term (A), the common ratio (R) and an integer N. Your task is to find the Nth term of the GP series.

The general form of a GP(Geometric Progression) series is A, A(R), A(R^2), A*(R^3) and so on where A is the first term of GP series

Note :

As the answer can be large enough, return the answer modulo 10^9 + 7.

Input format :

The first line of input contains an integer T denoting the number of queries or test cases. 

The first line of every test case contains three single space-separated integers N, A, and R denoting the term of GP series required, the first term, and the common ratio respectively.

Output format :

For each test case, print an integer denoting the Nth term of GP in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^8
0 <= A <= 50 
0 <= R <= 100

Time limit: 1 second

Accepted Answer

Brute force

The idea is to use the formulae, Nth term of GP = A*R^(N-1).
To calculate POW i.e R^(N-1) we will use a loop and the algorithm for the same will be as given below,
- Initialise POW = 1
- For N-1 number of times,
  - POW = POW * R
Return A * POW.

Space Complexity: O(1)Explanation:

O(1) per test case.

In the worst case, only constant space is required.

Time Complexity: O(n)Explanation:

O(N) per test case where N is the required term of series.

In the worst case, we will be running a loop for N-1 times.

Accepted Answer

Optimized Recursive approach

The idea is to use the formulae, Nth term of GP = A*R^(N-1).
To calculate POW i.e R^(N-1) we will use recursive method (powHelper(R, N-1)), and the algorithm for the same will be as given below,
long powHelper(R, N):
- If N is zero, return 1.
- Recursively find R raised to power N/2 and store in some variable let's say, temp, temp = powHelper(R, N/2).
- If N is even, return (temp^2)
- Otherwise, return R * (temp^2)
Return A * POW.

Space Complexity: O(logn)Explanation:

O(logN) per test case where N is the required term of series.

In the worst case, extra space will be used by the recursion stack as there can be a maximum of Log(N) number of recursive calls at a time.

Time Complexity: O(logn)Explanation:

O(logN) per test case where N is the required term of series.

The recursive relation for the above algorithm will be F(N) = F(N/2). Thus we will be making recursion calls till N / (2^k) becomes 1 which makes k = logN.

You are given the first term (A), the common ratio (R) and an integer N. Your task is to find the Nth term of the GP series.

The general form of a GP(Geometric Progression) series is A, A(R), A(R^2), A*(R^3) and so on where A is the first term of GP series

Note :

As the answer can be large enough, return the answer modulo 10^9 + 7.

Input format :

Output format :

Note :

Constraints :

Top Nagarro Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in Nagarro Associate Software Engineer