Incremental Partitioning
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.

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

Question

Incremental Partitioning

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.

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.

Accepted Answer

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.

Space Complexity: OtherExplanation:

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

A recursion stack of size K will be used.

Time Complexity: OtherExplanation:

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).

C++ (g++ 5.4)

/*

	Time complexity: O(N^K) 

	Space complexity: O(N^2 * K)

	

	Where N is the number of items and K is the number of groups. 

*/



int incrementalPartitioningHelper(int n, int k, int last)

{

	// base case

	if (k == 0)

	{

		return (n == 0);

	}



	const int mod = 1e9 + 7;



	int answer = 0;



	// try all possible sizes of Kth group

	for (int s = 1; s <= min(n, last); s++)

	{

		answer += incrementalPartitioningHelper(n - s, k - 1, s);

		answer = answer % mod;

	}



	return answer;

}



int incrementalPartitioning(int n, int k)

{

	return incrementalPartitioningHelper(n, k, n);

}

Accepted Answer

Using Memoization

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again.

Let's understand by an example:

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

With the initial call incrementalPartitioningHelper(16, 4, 5).

We can see that we are solving the problem incrementalPartitioningHelper(5, 1, 3) multiple times from 2 different recursive calls.

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

Algorithm:

The idea is to use memoization.
Create a 3D lookup table of size (N + 1) * (K + 1) * (N + 1) where N is the size of total items, and K is the total number of groups. Lookup table stores the solutions to the subproblems where lookUp[N][K][last] stores the answer for problems with constraints N, K, last.
Initialize the table by -1.
Now, we will call a recursive function ‘incrementalPartitioningHelper’ with the following algorithm :
Initial Call: incrementalPartitioningHelper (N, K, N, lookUp)
incrementalPartitioningHelper(N, K, last, lookUp):
- If(K == 0):
  - If N == 0, return 1
  - Else, return 0
- If lookUp[N][K][last] is not -1, we already have the answer, return lookUp[N][K][last].
- Create an answer variable to store the final answer.
- Now, we calculate the answer for every possible partition,
  For S in range 1 to min(last, N):
  - Increment the answer by incrementalPartitioningHelper(N - S, K - 1, S, lookUp)
- Store the answer in the lookup table as lookUp[N][K][last] = answer.
- Return the ‘answer’.

Space Complexity: OtherExplanation:

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

We are building the lookUp table of size (N + 1)^2 * (K + 1) to store values of N, last and K. Thus, the final space complexity is O(N^2 * K).

Time Complexity: OtherExplanation:

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

For each of the recursive calls, we have a total of O(N) possible values of S. So we need to try each and every value. Doing it for each of the N * N * K states gives us the total time complexity of O(N^3 * K).

Python (3.5)

'''

    Time complexity: O(N^3 * K) 
	Space complexity: O(N^2 * K)
	
	Where N is the number of items and K is the number of groups. 

'''


def incrementalPartitioningHelper(n, k, last, lookup):
    # base case
    if (k == 0):
        return (n == 0)

    # return if already computed
    if (lookup[n][k][last] != -1):
        return lookup[n][k][last]

    mod = 1000000007
    answer = 0

    # try all possible sizes of Kth group
    for s in range(1, min(n, last)+1):
        answer += incrementalPartitioningHelper(n - s, k - 1, s, lookup)
        answer = answer % mod

    # store the answer
    lookup[n][k][last] = answer
    return answer


def incrementalPartitioning(n, k):
    lookup = [[[-1 for i in range(n+1)] for j in range(k+1)]
              for t in range(n+1)]
    return incrementalPartitioningHelper(n, k, n, lookup)

C++ (g++ 5.4)

/*

	Time complexity: O(N^3 * K) 

	Space complexity: O(N^2 * K)

	

	Where N is the number of items and K is the number of groups. 

*/



#include 



int incrementalPartitioningHelper(int n, int k, int last, vector>> &lookup)

{

	if (k == 0)

	{

		// base case.

		return (n == 0);

	}



	// return if already computed.

	if (lookup[n][k][last] != -1)

	{

		return lookup[n][k][last];

	}



	const int mod = 1e9 + 7;



	int answer = 0;



	// try all possible sizes of the Kth group.

	for (int s = 1; s <= min(n, last); s++)

	{

		answer += incrementalPartitioningHelper(n - s, k - 1, s, lookup);

		answer = answer % mod;

	}



	// store the answer.

	return lookup[n][k][last] = answer;

}



int incrementalPartitioning(int n, int k)

{

	vector>> lookup(n + 1, vector>(k + 1, vector(n + 1, -1)));



	return incrementalPartitioningHelper(n, k, n, lookup);

}

Accepted Answer

Using Bottom-Up Approach

Instead of combining the smaller subproblems, we can solve smaller problems first.
We can make use of Dynamic Programming Paradigm to keep track of the previous states to avoid solving repeated subproblems.
Create a dp table of size (N) * (K) * (N) .
Let dp[N][K][last] be the number of ways to solve the problem, then we can calculate it using sum of all dp[N - S][K - 1][S] for each valid S where 1<= S <= last is the size of the Kth group.
The base condition is dp[0][0][S] = 1 for each S from 1 to N.

Algorithm:

L1: For each i from 1 to N:
- L2: For each j from 1 to K
  - L3: For each last from 1 to N:
    - For each S from 1 to min(i, last):
      - dp[i][j][last] += dp[i - S][j - 1][S]
      - Take the modulo with 1e9 + 7.
Return the value of dp[N][K][N].

Space Complexity: O(1)Explanation:

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

We are building the dp table of size N^2 * K to store values of N, last and K. Thus, the final space complexity is O(N^2 * K).

Time Complexity: OtherExplanation:

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

For each state of the dp table, we have a total of O(N) possible values of S. So we need to try each and every value. Doing it for each of the N * N * K states gives us the total time complexity of O(N^3 * K).

Python (3.5)

'''

    Time complexity: O(N^3 * K) 
	Space complexity: O(N^2 * K)
	
	Where N is the number of items and K is the number of groups. 

'''


def incrementalPartitioning(n, k):
    mod = 1000000007

    dp = [[[0 for i in range(n+1)] for j in range(k+1)]
          for t in range(n+1)]

    # base case
    for i in range(n+1):
        dp[0][0][i] = 1

    for i in range(1, n+1):
        for j in range(1, k+1):
            for last in range(1, n+1):
                # try all possible sizes of the jth group
                for s in range(1, min(i, last)+1):
                    dp[i][j][last] = (
                        dp[i][j][last] + dp[i - s][j - 1][s]) % mod

    # return the final answer
    return dp[n][k][n]

C++ (g++ 5.4)

/*

	Time complexity: O(N^3 * K) 

	Space complexity: O(N^2 * K)

	

	Where N is the number of items and K is the number of groups. 

*/



#include 



int incrementalPartitioning(int n, int k)

{

	int mod = 1e9 + 7;

	vector>> dp(n + 1, vector>(k + 1, vector(n + 1, 0)));



	// base case.

	dp[0][0] = vector(n + 1, 1);



	for (int i = 1; i <= n; i++)

	{

		for (int j = 1; j <= k; j++)

		{

			for (int last = 1; last <= n; last++)

			{

				// try all possible sizes of the jth group.

				for (int s = 1; s <= min(i, last); s++)

				{

					dp[i][j][last] = (dp[i][j][last] + dp[i - s][j - 1][s]) % mod;

				}

			}

		}

	}



	// return the final answer.

	return dp[n][k][n];

}

Accepted Answer

Efficient Approach

Consider we are filling the groups in reverse order, i.e. group[i] >= group[i+1].
Clearly the Kth group will be the one having minimum size.
If it has size of 1, we need to solve the problem for (N - 1, K - 1).
If it has size greater than 1 then clearly all others will also have size greater than 1. So if we subtract 1 from each of them, it will still be a valid solution.
So this gives the same number of solutions as (N - K, K).
Adding these two will give us the required solution.

Consider the following example:

We need to solve the problem for N = 8 and K = 4.
Consider the 4th group.
- It can have size 1. So clearly our problem reduces to N = 7, K = 3.
- Consider the division [1, 1, 1, 1]. If we try to make the last group size > 1 we need to increase the size of all the groups by 1 as well.
- So if [2, 2, 2, 2] is a solution then we can decrease every group by 1 to arrive at a solution [1, 1, 1, 1] and our problem reduces to smaller constraints.

Algorithm:

Make a dp table of size (N) * (K) with each element as 0.
Set base case as dp[0][0] = 1.
dp[i][j] denotes answer for the problem N = i and K = j;
L1: For each i from 1 to N
- L2: For each j from 1 to min(i, K)
  - Update dp[i][j] = dp[i-j][j] + dp[i-1][j-1].
  - Take modulo with 1e9 + 7.
Return dp[N][K].

Space Complexity: O(m*n) - For 2d arraysExplanation:

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

We are building the dp table of size N * K to store values of N and K. Thus, the final space complexity is O(N * K).

Time Complexity: O(m*n) - For 2d arraysExplanation:

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

We are filling the dp table of size N * K, thus the final time complexity is O(N * K).

C++ (g++ 5.4)

/*

	Time complexity: O(N * K) 

	Space complexity: O(N * K)

	

	Where N is the number of items and K is the number of groups. 

*/



#include 



int incrementalPartitioning(int n, int k)

{

	const int mod = 1e9 + 7;



	vector> dp(n + 1, vector(k + 1, 0));



	// base case.

	dp[0][0] = 1;



	for (int i = 1; i <= n; i++)

	{

		for (int j = 1; j <= min(i, k); j++)

		{

			// either make a new group with size 1 or add one to all the existing groups.

			dp[i][j] = (dp[i - j][j] + dp[i - 1][j - 1]) % mod;

		}

	}



	// return the final answer.

	return dp[n][k];

}

Python (3.5)

'''

    Time complexity: O(N * K) 
	Space complexity: O(N * K)
	
	Where N is the number of items and K is the number of groups. 

'''


def incrementalPartitioning(n, k):
    mod = 1000000007

    dp = [[0 for i in range(k+1)] for j in range(n+1)]

    # base case
    dp[0][0] = 1

    for i in range(1, n+1):
        for j in range(1, min(i, k)+1):
            # either make a new group with size 1 or add one to all the existing groups.
            dp[i][j] = (dp[i - j][j] + dp[i - 1][j - 1]) % mod

    # return the final answer
    return dp[n][k]

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.

Input format:

Output format:

Note:

Constraints:

Top Expedia Group Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Expedia Group Software Developer Intern