Last Updated: 29 Apr, 2021
Price Pattern
Easy
Asked in companies
Ninja observed the prices of a certain stock for some days. He found an interesting pattern in the prices of the stock. Let P(i) be the price of the stock on the ‘ith’ day. He observed that
P(i) = P(i-1) + P(i-2) + P(i-1) * P(i-2)
You are given the stock prices on the first day and the second day. Your task is to determine the price of the stock on the ‘Nth’ day if the prices followed the same pattern.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains three space-separated integers, ‘A’, ‘B’ and ‘N’ Where ‘A’ and ‘B’ denote the prices on the first and second days respectively. ‘N’ denotes the day on which the stock price needs to be calculated.
Output Format :
For each test case, print a single integer, denoting the price of the stock on the ‘Nth’ day. Since the answer can be very large, calculate the answer modulo 10^9+7.
Output for each test case will be printed 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 <= A,B, <= 10^9
3 <= N <= 5000
Time Limit: 1sec
Approaches
Approach:
The approach is to simply call the function recursively to find the prices on the last day and the second last day. These two values can then be used to calculate the prices for the current day.
Steps:
- If N = 1, return ‘A’, because ‘A’ is the price of the stock on day 1.
- If N = 2, return ‘B’, because ‘B’ is the price of the stock on day 2.
- Now, store the result of findPrice(a,b,n-1) in a variable, say lastDayPrice.
- Store the result of findPrice(a,b,n-2) in a variable, say scndLastDayPrice.
- Now we can simply return the value of lastDayPrice + scndLastDayPrice + (lastDayPrice * scndLastDayPrice).
Approach:
The approach is to store the result for smaller subproblems so that we don’t have to recalculate the result for the same subproblem multiple times. We can create a vector to store the results. First, initialize all the elements in it with a particular value. After finding the result of a subproblem, update this value at the corresponding position. Before solving the result for any subproblem, we can check whether the result for this problem has already been solved or not.
Steps:
- Create a vector, say memo, of size ‘N+1’, and initialize all values to -1. We choose this value because we know that this value can never be the price of the stock on any day.
- Now, make memo[1]=A and make memo[2]=B.
- Now, simply return the result of calcPrice(n, memo).
Int calcPrice(n, memo) {
- We already know the prices for day 1 and day 2 and we have stored the same in memo. So, if n==1 or n==2, simply return the value at memo[n].
- Now, check the value present at memo[n]. If this is not equal to -1, then that means that we have already solved this subproblem before so we can simply return the value present at memo[n].
- Else, make memo[n] = calcPrice(n-1,memo) + calcPrice(n-2,memo) + (calcPrice(n-1,memo) * calcPrice(n-2,memo)).
- Return the value at memo[n].
Approach:
The approach is to store the result for smaller subproblems and use these values to calculate prices for the next days. We can create a vector to store the results.
Steps:
- Create a vector, say dp, of size ‘N+1’.
- Make dp[1]=’A’ and make dp[2]=’B’.
- Run a loop from i=3 to i<=N, and do:
- Make dp[i] = dp[i-1] + dp[i-2] + (dp[i-1] * dp[i-2]).
- Return the value stored at dp[n]. This value is the price of the stock on the ‘Nth’ day.