Count Ways to Distribute N Chocolates among K persons
Given N Chocolates, distribute them among K Persons. We are also given an array of maxChocolates[] of size K. The Chocolates can be distributed in such a manner that the ith person has the capacity maxChocolates[i] (both inclusive). Find the total number of ways to distribute the chocolates such that no chocolates are left, and no person gets more chocolate than his capacity.
Examples:
Input: N = 3, K = 2, maxChocolates = [2, 3]
Output: 3
Explanation: There are 3 ways to distribute the chocolates:
- Person1 gets 0 chocolate and Person2 gets 3 chocolates.
- Person1 gets 1 chocolate and Person2 gets 2 chocolates.
- Person1 gets 2 chocolates and Person2 gets 1 chocolate.
Input: N = 4, K = 2, maxChocolates = [1, 1]
Output: 0
Explanation: There is no way to distribute the 4 chocolates among these 2 persons.
Approach: The problem can be solved using the following appraoch:
The problem can be solved using Dynamic Programming. We can maintain a 2D array dp[][] such that dp[i][j] will store the number of ways to distribute i chocolates among j persons. Now, we iterate over all the persons, and for every person i, we explore all the possibilities of distributing the chocolates to the ith person.
dp[i][j] = number of ways to distribute i chocolates till the person at index j
Follow the steps mentioned below to implement the idea:
- Declare a method countWays(i, remainingChocolates) which gives us the number of ways to distribute the remaining chocolates among the persons from index 0 to index i.
- If i < 0, then we don’t have any person left to give the chocolates to, so check if remainingChocolates is equal to zero as we need to distribute all the chocolates.
- Check dp[i][remainingChocolates] to prevent unnecessary recursion calls.
- Maintain count = 0 to store the number of ways
- Explore all the possible cases by assigning the ith person 0,1,2 … to minimum of the capacity of ith person and remainingChocolates and add their answers to count.
- Return count to get the answer.
Below is the implementation of the above appraoch:
#include <bits/stdc++.h>
using namespace std;
// Method to find the total number of ways
int countWays(int* maxChocolates, int i,
int remainingChocolates,
vector<vector<int> >& dp)
{
if (i == -1) {
if (remainingChocolates == 0)
return 1;
return 0;
}
// Check if we have previously calculated the answer
if (dp[remainingChocolates][i] != -1)
return dp[remainingChocolates][i];
// count variable to store the number of ways
int count = 0;
// For person i, assign him 0, 1, 2 ....
// .. maxChocolates[i] chocolates
for (int c = 0;
c <= min(maxChocolates[i], remainingChocolates);
c++) {
count += countWays(maxChocolates, i - 1,
remainingChocolates - c, dp);
}
return dp[remainingChocolates][i] = count;
}
int main()
{
int n = 3, k = 2;
int maxChocolates[k] = { 2, 3 };
vector<vector<int> > dp(n + 1, vector<int>(k, -1));
// dp[i][j] = number of ways to distribute i chocolates
// till person at index j
cout << countWays(maxChocolates, k - 1, n, dp) << "\n";
// your code goes here
return 0;
}
/*code by Flutterfly*/
import java.util.Arrays;
public class ChocolateDistribution {
// Method to find the total number of ways
public static int countWays(int[] maxChocolates, int i, int remainingChocolates, int[][] dp) {
// Base case: If there are no more people to distribute chocolates to
if (i == -1) {
return remainingChocolates == 0 ? 1 : 0;
}
// Check if the result for this state is already calculated
if (dp[remainingChocolates][i] != -1) {
return dp[remainingChocolates][i];
}
int count = 0;
// For person i, assign him 0, 1, 2, ..., maxChocolates[i] chocolates
for (int c = 0; c <= Math.min(maxChocolates[i], remainingChocolates); c++) {
count += countWays(maxChocolates, i - 1, remainingChocolates - c, dp);
}
// Memoize the result and return
dp[remainingChocolates][i] = count;
return count;
}
public static void main(String[] args) {
int n = 3, k = 2;
int[] maxChocolates = {2, 3};
int[][] dp = new int[n + 1][k];
// Initialize the dp array with -1
for (int[] row : dp) {
Arrays.fill(row, -1);
}
System.out.println(countWays(maxChocolates, k - 1, n, dp));
}
}
# code by flutterfly
def count_ways(max_chocolates, i, remaining_chocolates, dp):
# Base case: If there are no more people to distribute chocolates to
if i == -1:
return 1 if remaining_chocolates == 0 else 0
# Check if the result for this state is already calculated
if dp[remaining_chocolates][i] != -1:
return dp[remaining_chocolates][i]
count = 0
# For person i, assign him 0, 1, 2, ..., max_chocolates[i] chocolates
for c in range(min(max_chocolates[i], remaining_chocolates) + 1):
count += count_ways(max_chocolates, i - 1, remaining_chocolates - c, dp)
# Memoize the result and return
dp[remaining_chocolates][i] = count
return count
def main():
n, k = 3, 2
max_chocolates = [2, 3]
dp = [[-1] * k for _ in range(n + 1)]
print(count_ways(max_chocolates, k - 1, n, dp))
if __name__ == "__main__":
main()
//code by Flutterfly.
using System;
class Program
{
static int CountWays(int[] maxChocolates, int i, int remainingChocolates, int[,] dp)
{
// Base case: If there are no more people to distribute chocolates to
if (i == -1)
{
return remainingChocolates == 0 ? 1 : 0;
}
// Check if the result for this state is already calculated
if (dp[remainingChocolates, i] != -1)
{
return dp[remainingChocolates, i];
}
int count = 0;
// For person i, assign him 0, 1, 2, ..., maxChocolates[i] chocolates
for (int c = 0; c <= Math.Min(maxChocolates[i], remainingChocolates); c++)
{
count += CountWays(maxChocolates, i - 1, remainingChocolates - c, dp);
}
// Memoize the result and return
dp[remainingChocolates, i] = count;
return count;
}
static void Main()
{
int n = 3, k = 2;
int[] maxChocolates = { 2, 3 };
int[,] dp = new int[n + 1, k];
// Initialize the dp array with -1
for (int i = 0; i <= n; i++)
{
for (int j = 0; j < k; j++)
{
dp[i, j] = -1;
}
}
Console.WriteLine(CountWays(maxChocolates, k - 1, n, dp));
}
}
function countWays(maxChocolates, i, remainingChocolates, dp) {
// Base case: If there are no more people to distribute chocolates to
if (i === -1) {
return remainingChocolates === 0 ? 1 : 0;
}
// Check if the result for this state is already calculated
if (dp[remainingChocolates][i] !== -1) {
return dp[remainingChocolates][i];
}
let count = 0;
// For person i, assign him 0, 1, 2, ..., maxChocolates[i] chocolates
for (let c = 0; c <= Math.min(maxChocolates[i], remainingChocolates); c++) {
count += countWays(maxChocolates, i - 1, remainingChocolates - c, dp);
}
// Memoize the result and return
dp[remainingChocolates][i] = count;
return count;
}
function main() {
const n = 3, k = 2;
const maxChocolates = [2, 3];
const dp = Array.from({ length: n + 1 }, () => Array(k).fill(-1));
console.log(countWays(maxChocolates, k - 1, n, dp));
}
main();
Output
3
Time Complexity: O(N * K * K), where N is the number of chocolates and K is the number of persons.
Auxiliary Space: O(N * K)
Approach 2: Using Iterative approach:
This iterative approach avoids recursion and calculates the result in a bottom-up manner using dynamic programming.
- Create a 2D array dp of size (N+1) x (K+1) to store the number of ways to distribute i chocolates among j persons.
- Initialize dp[i][0] to 1 for all i from 0 to N as there is only one way to distribute chocolates among 0 persons (i.e., no one).
- Iterate over the persons from 1 to K and for each person j, iterate over the chocolates from 1 to N.
- For each combination of person j and remaining chocolates i, calculate dp[i][j] by summing up the possibilities of assigning 0, 1, 2, …, min(maxChocolates[j], i) chocolates to person j.
- The answer will be stored in dp[N][K], representing the number of ways to distribute N chocolates among K persons.
#include <bits/stdc++.h>
using namespace std;
int countWays(int N, int K, int maxChocolates[]) {
vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));
// Base case: There is one way to distribute 0 chocolates among any number of persons.
for (int i = 0; i <= K; ++i)
dp[0][i] = 1;
// Iterate over persons and chocolates
for (int j = 1; j <= K; ++j) {
for (int i = 1; i <= N; ++i) {
// Calculate dp[i][j] by summing up possibilities
for (int c = 0; c <= min(maxChocolates[j - 1], i); ++c) {
dp[i][j] += dp[i - c][j - 1];
}
}
}
return dp[N][K];
}
int main() {
int N = 3, K = 2;
int maxChocolates[] = {2, 3};
cout << countWays(N, K, maxChocolates) << "\n";
return 0;
}
import java.io.*;
public class GFG {
public static int countWays(int N, int K, int[] maxChocolates) {
// Initialize a 2D array to the store the number of ways
int[][] dp = new int[N + 1][K + 1];
// Base case: There is one way to the distribute 0 chocolates among any number of persons.
for (int i = 0; i <= K; i++) {
dp[0][i] = 1;
}
// Iterate over persons and chocolates
for (int j = 1; j <= K; j++) {
for (int i = 1; i <= N; i++) {
for (int c = 0; c <= Math.min(maxChocolates[j - 1], i); c++) {
dp[i][j] += dp[i - c][j - 1];
}
}
}
return dp[N][K];
}
public static void main(String[] args) {
int N = 3; // Number of chocolates
int K = 2; // Number of persons
int[] maxChocolates = {2, 3};
// Printing the result
System.out.println(countWays(N, K, maxChocolates));
}
}
function countWays(N, K, maxChocolates) {
// Initialize a 2D array to store the number of ways
const dp = Array.from({ length: N + 1 }, () => Array(K + 1).fill(0));
// Base case: There is one way to distribute 0 chocolates among any number of persons.
for (let i = 0; i < K + 1; i++) {
dp[0][i] = 1;
}
// Iterate over persons and chocolates
for (let j = 1; j < K + 1; j++) {
for (let i = 1; i < N + 1; i++) {
// Calculate dp[i][j] by summing up possibilities
for (let c = 0; c <= Math.min(maxChocolates[j - 1], i); c++) {
dp[i][j] += dp[i - c][j - 1];
}
}
}
return dp[N][K];
}
// Testing the function
const N = 3; // Number of chocolates
const K = 2; // Number of persons
const maxChocolates = [2, 3]; // Maximum number of chocolates each person can have
// Printing the result
console.log(countWays(N, K, maxChocolates));
def count_ways(N, K, max_chocolates):
# Initialize a 2D array to store the number of ways
dp = [[0] * (K + 1) for _ in range(N + 1)]
# Base case: There is one way to distribute 0 chocolates among any number of persons.
for i in range(K + 1):
dp[0][i] = 1
# Iterate over persons and chocolates
for j in range(1, K + 1):
for i in range(1, N + 1):
# Calculate dp[i][j] by summing up possibilities
for c in range(min(max_chocolates[j - 1], i) + 1):
dp[i][j] += dp[i - c][j - 1]
return dp[N][K]
if __name__ == "__main__":
N = 3 # Number of chocolates
K = 2 # Number of persons
max_chocolates = [2, 3] # Maximum number of chocolates each person can have
# Printing the result
print(count_ways(N, K, max_chocolates))
Output
3
Time Complexity: O(N * K * maxChocolates_max), where maxChocolates_max is the maximum value in the maxChocolates array.
Auxiliary Space: O(N * K)