Shopping Spree
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?

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

Question

Shopping Spree

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?

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

Accepted Answer

Firstly, I solved using array but all my test cases were not passed then I solved with dp approach by which all test cases passed successfully.

Accepted Answer

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.

Space Complexity: OtherExplanation:

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.

Time Complexity: OtherExplanation:

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

Accepted Answer

Memoization

Let’s understand by an example.

Suppose we have three items in the shop and Preeti can buy at most four items.

The below figure shows some of the recursive calls for the given problem.

Note: Subproblem {a,b} means a problem with ‘a’ items and ‘b’ is the number of items Preeti is willing to buy.

As we can see, some subproblems are called multiple times.

For example, the subproblem {2,3} is called 2 times, {1, 3} is called 3 times, {1, 1} is called numerous times.

That’s why we will store the solved subproblems in a lookup table so that we don’t have to solve them again. Whenever there is a call to the solved subproblem, we will directly return the answer of that subproblem stored in the lookup table.

The idea is to use memoization.
Create a 2D lookup table to store the solutions to the subproblems where lookUp[i][j] denotes the possible number of ways to get j items with i available items.
Initialize all cells of the table by -1 to indicate that any of the subproblems is not solved.
Now, we call a helper function that returns us the number of combinations using N items and buying at most K items and stores it in a variable to say the ans.
The algorithm for the helper function will be as follows:

Int helper(N, K):
A. If N or K becomes 0, return 0.
B. If lookUp[N][K] is not equal to -1, return lookUp[N][K].
C. Update lookUp[N][K] with helper(N-1, K) + helper(N, K-1) + 1.
D. Return lookUp[N][K].
Return ans.

Space Complexity: OtherExplanation:

O(N * K) per test case where N is the number of available items, and K is the maximum number of items allowed.

In the worst case, we are using a memoization table of size N*K.

Time Complexity: OtherExplanation:

O(N * K) per test case, where N is the number of available items, and K is the maximum number of items allowed.

In the worst case, the maximum number of calls made is N*K when one subproblem is repeated, we return the fetched answer and do not explore it further.

Accepted Answer

Dyncamic Programming

The idea is to create a 2-D table DP with row size N+1 and column size K+1.
Initially, all the elements of the DP table will be 0.
Now, the value DP[i][j] means the possible number of ways to shop at most j items from the available i items.
The detailed algorithm to fill the DP table will be as follows:
- Loop 1: For i = 1 to N:
- Loop 2: For j = 1 to K:
  DP[ i ][ j ] = DP[i - 1 ][ j ] + DP[ i ][ j - 1 ] + 1
Return DP[N][K].

Let us understand the above algorithm in detail with an example:

For the test case where N = 3 and K = 4.

We will create a DP table with 4 (N + 1) rows and 5 columns (K +1) with all elements as 0.
In the next step when we are at DP[1][1], this means that we have to fill the number of ways to buy at most 1 item from the available 1 item in the shop. This can be found by:-
-> Finding the answer to number of ways to buy at most 0 items from 1 available item i.e { NULL }, DP[1][0].
-> Finding the answer to number of ways to buy at most 1 item from 0 available items i.e { NULL }, DP[0][1].
-> Adding 1 as we will add the new item say {R}.

Thus, DP[1][1] = 1.
Similarly, for DP[1][2] will be DP[0][2] + DP[1][1] + 1. Which is DP[0][2] = { NULL }, DP[1][1] = {R} and +1 for adding {RR} to the set as well as we can buy 2 items this time.
Thus, DP[1][2] is {(R), (RR)}

The table will be:

To make it more clear, let the first item be R, second be G and third be B, The list will be:-

Space Complexity: OtherExplanation:

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, we are using a DP table of size N * K.

Time Complexity: OtherExplanation:

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, we will be using 2 nested loops. Thus, O(N * K).

Accepted Answer

Combinatorics

You can recall that out of N items, Preeti can buy 1 to K items. Thus, the total number of ways to buy at most K items from the given N items is:-
WAYS(N, K) = WAYS(N, 1) + WAYS(N, 2) + ……….WAYS(N, K)
If you observe, this takes us to the formulae:-
If N == 1, WAYS(N, K) = 1
Otherwise, WAYS(N, K) = nCr(N + K - 1, K). K >= 1
The idea is to solve the above formulae and return the outcome.

Algorithm:

Initialize variable res to store the result.
For i from 1 to K,
- res += nCr(N+K-1, K)
Return res

This can be calculated efficiently in O(K) using python.

int shoppingSpree(int N, int K):

Initialize answer = 0, fact = 1, num = 1, mod = 10^9+7.
For i from 1 to K,
- fact *= i
- num *= N+K-1
- answer = (num // fact) % mod
Return answer.

Space Complexity: O(1)Explanation:

O(1) per test case,

In the worst case, constant extra space is used.

Time Complexity: O(n)Explanation:

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

In the worst case, K calls are made which take constant time to execute.

Note:

Follow Up:

Input format:

Output format:

Note:

Constraints:

Top Barclays Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Barclays Software Developer