Price Pattern

Easy
0/40
Average time to solve is 15m
profile
Contributed by
10 upvotes
Asked in companies
Providence Global Center LLPGoogle inc

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

1
1 7 3

Sample Output 1 :

15

Explanation For Sample Input 1 :

In the given test case, the price on day 1 is 1, and the price on day 2 is 7. We can calculate the price on day 3 using these two values. Price on day 3 will be 1 + 7 + (1*7) = 15.

Sample Input 2 :

1
1 3 4

Sample Output 2 :

31

Explanation For Sample Input 2 :

In the given test case, the price on day 1 is 1, and the price on day 2 is 3. We can calculate the price on day 3 using these two values. Price on day 3 will be 1 + 3 + (1*3) = 7. Similarly, price on day 4 will be 3 + 7 + (3*7) = 31.
Hint

Find the price for previous days by recursively calling the function for that day.

Approaches (3)
Using Recursion

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:

  1. If N = 1, return ‘A’, because ‘A’ is the price of the stock on day 1.
  2. If N = 2, return ‘B’, because ‘B’ is the price of the stock on day 2.
  3. Now, store the result of findPrice(a,b,n-1) in a variable, say lastDayPrice.
  4. Store the result of findPrice(a,b,n-2) in a variable, say scndLastDayPrice.
  5. Now we can simply return the value of lastDayPrice + scndLastDayPrice + (lastDayPrice * scndLastDayPrice).
Time Complexity

O(2 ^ N), where ‘N’ is the day for which the price is to be calculated.

 

We are recursively calling the function for smaller subproblems which in turn are calling the same function for even smaller subproblems. This takes O(2^N) time as for every function call, we need values of two smaller subproblems.

Space Complexity

O(2 ^ N), where ‘N’ is the day for which the price is to be calculated.

 

We need extra space for the recursion stack.

Code Solution
(100% EXP penalty)
Price Pattern
Full screen
Console