Last Updated: 15 Oct, 2020
N-th Term Of GP
Easy
Asked in companies
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
Approaches
- 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.
- 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.