Chocolates

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
4 upvotes
Asked in companies
UberCodenation

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 2
4 4
Sample Output 1:
3
1
Explanation for Sample Input 1:
For case 1:
Three valid packagings are as follows:
Any one among [{1, 2}, {3}] , [{2, 1}, {3}] , [{3}, {1, 2}] and [{3}, {2, 1}], as all of these are considered same.
Any one among [{2, 3}, {1}] , [{3, 2}, {1}] , [{1}, {2, 3}] and [{1}, {3, 2}].
Any one among [{1, 3}, {2}] , [{3, 1}, {2}] , [{2}, {1, 3}] and [{2}, {3, 1}].

For Case 2:
The only way is to pack one chocolate in each bag.
Sample Input 2:
3
3 1
5 2
6 3
Sample Output 2:
1
15
90
Hint

Select all the chocolates one by one, and find all possible ways to pack them.

Approaches (2)
Brute Force

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 - 

  1. 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).
  2. 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.
Time Complexity

O(2 ^ N), where 'N' is the number of chocolates.

There are two recursive calls for each of the 'N' chocolates. Hence overall time complexity becomes (2 ^ N).

Space Complexity

O(N), where 'N' is the number of chocolates.

Apart from recursion, constant space is used. The maximum stack size for recursion on 'N' elements is O(N). Hence overall space complexity becomes O(N).

Code Solution
(100% EXP penalty)
Chocolates
Full screen
Console