Incremental Partitioning

Easy
0/40
1 upvote
Asked in companies
Expedia GroupD.E.Shaw

Problem statement

You are given two integers N and K, you need to find the number of ways to divide N into k non-empty groups such that size of group[i] >= group[i - 1] for each valid i. Print it modulo 1e9 + 7.

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of  every test case contains 2 space separated integers N and K.
Output format: 
For each test case, print the required number of ways modulo 1e9 + 7. 

The output for each test case is 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. DON'T forget to print modulo 1e9 + 7.
Constraints: 
1 <= T <= 10 
1 <= N <= 1000
1 <= K <= N

Where T is the number of test cases, N is the total number of items and K is the number of groups.
Sample Input 1:
1
4 2
Sample Output 1:
2
Explanation of Sample Input 1:
There are 2 groups such that their sum is 4.
These are : [1, 3], [2, 2]
Note: You can’t have [3, 1] because it will have size of group[0] > group[1].
Sample Output 2:
1
4 4
Sample Output 2:
1
Explanation of Sample Input 2:
[1, 1, 1, 1] is the only way to divide 4 into 4 groups with the given condition.
Hint

What is the recurrence relation ?

Approaches (4)
Using Recursion
  • We can use a recursive approach to find the number of ways to divide N into K groups incrementally.
  • Our current answer depends on the number of items we have (N), the number of groups we are left with and the size of the last group we used.
  • Say we are in the ith group. We can try to fill the current group with every possible number and then solve the problem with smaller constraints.
  • So let incrementalPartitioningHelper(N, K, last) be the answer for the given problem, then we can try each possible size of the Kth group from 1 to last, say S, then we are left with a subproblem with remaining items
    • N -> N - S
    • K -> K - 1
    • last  -> S
  • Note that we are trying to fill the Kth group, considering that the size of the (K+1)th group is ‘last’. Thus, the possible size of the Kth group is in the range [1, last] as group[i] <= group[i + 1].
  • So for each possible value of S, we add incrementalPartitioningHelper(N - S, K - 1, S) to our current answer.
  • Finally we have a base condition as incrementalPartitioningHelper(0, 0 , S) = 1 for every S.
Time Complexity

O(N ^ K), Where N is the number of items and K is the number of groups . 

 

Every time we decrement K by 1, our problem can be reduced into O(N) different subproblems.

So, Time complexity = N * N * N… N (K times) = O(N^K).

Space Complexity

O(K), where K is the number of groups.
 

A recursion stack of size K will be used. 

Code Solution
(100% EXP penalty)
Incremental Partitioning
Full screen
Console