Last Updated: 8 Dec, 2021
Chocolates
Moderate
Asked in companies
You have 'N' chocolates and 'K' empty bags. Your task is to pack all the chocolates in these bags such that any bag can have any number of chocolates, but no bag remains empty. Please note that all the chocolates are different, i.e., they can be numbered from 1 to 'N', but all bags are identical.
E.g., If there are 3 chocolates and 2 bags, then you can pack the chocolates in the following three ways -
[1, 2] and [3].
[2, 3] and [1].
[1, 3] and [2].
Only the above three packings are considered valid. Some more packages are possible; for example, packing [{2}, {3, 1}] is not taken because [{1, 3}, {2}] is already considered, i.e., order of bags and the order of chocolates inside a bag don't matter.
You are given the number of chocolates 'N' and the number of bags 'K'. Find the number of ways to pack the chocolates. Return your answer modulo 10^9+7.
Input Format:
The first line contains 'T', denoting the number of tests.
For each Test :
The only line contains two space-separated integers, 'N' and 'K', denoting the number of chocolates and bags, respectively.
Output Format:
For each test, print one integer, denoting the number of valid ways (modulo 10^9+7) to pack given 'N' chocolates into 'K' bags.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 10
1 <= 'K' <= 'N' <= 10^3
Time Limit: 1 sec
Approaches
Approach: There are 'N' chocolates and 'K' bags; assume that you have solved N-1 chocolates and now solve N-th chocolate.
There will be two ways to pack this chocolate -
- All 'K' bags are already non-empty, so that you can put this chocolate in any of the 'K' bags. Each bag has some chocolates, so putting it in any bag generates a new packaging, i.e., Solution(N, K) = K * Solution(N-1, K).
- One or more bags are empty till the moment, so pack N-th chocolate in an empty bag. All empty bags are identical, so Solution (N, K) = Solution(N-1, K-1).
Merging both possibilities, Solution(N, K) = K * Solution(N-1, K) + Solution(N-1, K-1).
Repeat the same process for each chocolate, i.e., solve for i-th chocolate, assuming that you have a solution for (i-1) chocolates.
Algorithm:
- Create a recursion, which accepts two parameters, N and K.
- Check for the base cases; if there is no chocolate or no bag or chocolates are less than empty bags, return 0.
- If only one bag or number of chocolates equals to bags, return 1.
- Call recursion; return K * recursion(N-1, K) + recursion(N-1, K-1).
- From the main function, call recursion on (N, K). The returned value is our desired answer.
Approach: In the Brute force approach, to solve a pair (N, K), two calls (N-1, K) and (N-1, K-1) are made, which results in the same calculation multiple times. Please see the image below for better understanding.
We can see that when a recursion is called on pair (10, 7), pair (8, 6) is calculated multiple times, and there are many more pairs in the subtree.
A dp of size N*K is made to optimize this thing, which stores the result for each pair (N, K), and no pair is calculated multiple times.
Algorithm:
- Create a dp of size N*K and initialize with 0.
- Iterate a for loop, i = 1 to N.
- Iterate another for loop, j = 1 to K.
- If the number of chocolate and bags are equal, i.e, i == j, fill dp[i][j] as 1.
- If there is only one bag, i.e., j == 1, fill dp[i][j] as 1.
- Fill the dp as per the recursion rule, i.e., dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1].
- Iterate another for loop, j = 1 to K.
- Finally return the value dp[N][K].
Similar problems