Shopping Spree

Hard
0/120
Average time to solve is 50m
8 upvotes
Asked in companies
BarclaysAmdocsGoogle inc

Problem statement

Preeti has decided to go to the Grand Mall to buy some stuff for her father’s birthday. On reaching the place, she found a fascinating shop that has an unlimited quantity of each item they sell. The shop has N different types of items. However, here Preeti has a fixed budget and can buy a maximum of K items. She can buy any amount of items ≥ 1 and ≤ K.

She can buy an arbitrary quantity of each item. There is no restriction on different items having different quantities. Now, Preeti wonders the number of different ways in which she can shop today. Two ways are considered different if the quantity of at least 1 of the items purchased is different. Preeti finds this task too hard to complete and requires your help. Your task is to find the required answer.

Note: 
As the answer can be large, return your answer modulo 10^9  + 7.
Follow Up: 
Can you solve this using constant extra space?
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer T denoting the number of queries or test cases. 

The first and the only line of every test case contains 2 integers N and K representing the different number of items at the shop and maximum items Preeti can buy respectively.
Output format: 
For each test case, print the number of different ways to buy in a single 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 <= 1000
1 <= K <= 1000 

Time Limit: 1 sec
Sample Input 1:
3
1 1
1 3
3 2
Sample Output 1:
1
3
9
Explanation For Sample Input 1 :
For test case 1:  
There is 1 item in the shop and Preeti can buy at most 1 item.

The only possible way of shopping this way is 1.  

For test case 2:
There is 1 item in the shop and Preeti can buy at most 3 items.

Suppose the item in the shop is named as R. The only possible ways of shopping this way are {(R), (RR), (RRR)}.  

For test case 3:
There are 3 items in the shop and Preeti can buy at most 2 items.

Suppose the items in the shop are named as R, G and B. The possible ways of shopping this way are {(R), (G), (B), (RR), (BB), (GG), (RG), (RB), (BG)}.
Sample input 2:
2
3 3
4 3
Sample output 2:
19
34
Hint

Try to break the big problem into several small subproblems.

Approaches (4)
Recursion
  • The idea is to use recursion to reduce the big problem into several small subproblems.
  • We will call a helper function that returns us the possible number of ways to shop.


Now, let us understand how to break the big problem into small subproblems with an example let's say, for N = 2 and K = 3 and let the items be {R, G} we can see that this can be found out if:

 

  • We know the possible answer for buying at most 3 items if only 1 item is available, i.e. {(R), (RR), (RRR)}.
  • We know the possible answer for buying at most 2 items if 2 items are available, i.e. {(R), (G), (RG), (RR), (GG)}, now, as we want the answer for at most 3 items, we will add the left out colour from the above point (G) to all the items which will make it {(RG), (GG), (RGG), (RRG), (GGG)}.
  • Also, we will add a single color (G) to the set.
  • This makes: {(R), (RR), (RRR), (RG), (GG), (RGG), (RRG), (GGG), (G)}, the answer becomes 9.
  • This makes F(N = 2, K = 3) = F(N = 1, K = 3) + F(N = 2, K = 2) + 1.

 

The algorithm for the helper function will look as follows: 
N = Number of available items. 
K = The highest number of items Preeti can buy. 

int helper(N, K):

 

  • If N or K becomes 0, return 0.
  • Return helper(N-1, K) + helper(N, K-1) + 1.
Time Complexity

O(2 ^ (N + K)) per test case where N is the number of available items, and K is the maximum number of items that can be bought.

 

In the worst case, we are making 2 calls for every function and the tree is going at a max depth of N + K

Space Complexity

O(N + K) per test case where N is the number of available items and K is the maximum number of items that can be bought.

 

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

Code Solution
(100% EXP penalty)
Shopping Spree
Full screen
Console