Pen Distribution Problem In C++

Introduction:

The Pen Distribution Problem is the classic combinatorial problem that appears in competitive programming, discrete mathematics and computer science. It is a great example of how real-life scenarios can be mathematically modeled. It is related to distributing a fixed number of identical items (pens) to a group of people while ensuring that we fulfill certain rules and restrictions on that Distribution.

Combinatorics: It is a question of counting all the ways that we can distribute items. There are a lot of 'combinatorics' combinatorial techniques, such as combinations, permutations and the stars and bars method used.

Indistinguishable Objects: The pens are indistinguishable (identical items), and the people to whom they are assigned are distinguishable (different individuals). This distinction is important because problem-solving looks different.

Constraints and Variants: The constraints that change the nature of the solution for the problem are different.

Unrestricted Distribution: If we 'lose' any number of pens, any person may receive that Number of pens (including zero).

At least one pen per person: Each pen is to be given to at least one person.

At most, we can only give one pen per person. We can only give out one pen to a person (or two if you pair with a partner).

Knowing about these constraints will help us to decide what approach works best for each variant mathematically.

Approach-1: Brute Force Method

The brute force approach is the most obvious way to solve the Pen Distribution Problem, either for the first time we have learned the problem or if we are dealing with small input sizes. It means not using any specific mathematical formula to assign the pens to the people; instead, it consists of systematically creating all distributed manner ways to give the pens to the people. In the brute force technique, the exhaustive search is applied to the slice. Every combination of the pen distributions is explored, checked, and counted by following the problem's constraints.

Example:

Let us take an example to illustrate the Pen Distributing Problem in C++ using the Brute Force method.

Example


#include <iostream>
#include <vector>
using namespace std;
//Function for unrestricted Distribution of pens
int countWaysUnrestricted(int n, int k, vector<int>& distribution) {
    if (n == 0) {
        // Print the current valid Distribution
        for (int pens : distribution) {
            cout << pens << " ";
        }
        cout << endl;
        return 1;
    }
    if (k == 0) return 0;
    int count = 0;
    // Try giving any number of pens (0 to n) to the current person
    for (int i = 0; i <= n; ++i) {
        distribution.push_back(i);
        count += countWaysUnrestricted(n - i, k - 1, distribution);
        distribution.pop_back(); // Backtrack to try another distribution
    }
    return count;
}
//Function for Distribution with each person receiving at least one pen
int countWaysAtLeastOne(int n, int k, vector<int>& distribution) {
    if (n == 0 && k == 0) {
        // Print the current valid Distribution
        for (int pens : distribution) {
            cout << pens << " ";
        }
        cout << endl;
        return 1;
    }
    if (n <= 0 || k <= 0) return 0;
    int count = 0;
    // Ensure each person receives at least one pen
    for (int i = 1; i <= n; ++i) {
        distribution.push_back(i);
        count += countWaysAtLeastOne(n - i, k - 1, distribution);
        distribution.pop_back(); // Backtrack
    }
    return count;
}
//Function for Distribution where each person can receive at most one pen
int countWaysAtMostOne(int n, int k, vector<int>& distribution) {
    if (n == 0) {
        // Print the current valid Distribution
        for (int pens : distribution) {
            cout << pens << " ";
        }
        cout << endl;
        return 1;
    }
    if (k == 0 || n > k) return 0;
    int count = 0;
    // Give one pen to the current person or skip them
    distribution.push_back(1);
    count += countWaysAtMostOne(n - 1, k - 1, distribution);
    distribution.pop_back(); // Backtrack
    distribution.push_back(0);
    count += countWaysAtMostOne(n, k - 1, distribution);
    distribution.pop_back(); // Backtrack
    return count;
}
//Function for exactly equal Distribution of pens (n must be divisible by k)
int countWaysEqualDistribution(int n, int k, vector<int>& distribution) {
    if (n % k != 0) return 0; // Impossible to equally distribute
    int pensPerPerson = n / k;
    for (int i = 0; i < k; ++i) {
        distribution.push_back(pensPerPerson);
    }
    // Print the current valid equal Distribution
    for (int pens : distribution) {
        cout << pens << " ";
    }
    cout << endl;
    return 1;
}
//Function for Distribution with a maximum limit of pens per person
int countWaysWithMaxLimit(int n, int k, int maxPens, vector<int>& distribution) {
    if (n == 0) {
        // Print the current valid Distribution
        for (int pens : distribution) {
            cout << pens << " ";
        }
        cout << endl;
        return 1;
    }
    if (k == 0) return 0;
    int count = 0;
    // Distribute pens with a maximum limit for each person
    for (int i = 0; i <= min(n, maxPens); ++i) {
        distribution.push_back(i);
        count += countWaysWithMaxLimit(n - i, k - 1, maxPens, distribution);
        distribution.pop_back(); // Backtrack
    }
    return count;
}
int main() {
    int n, k, maxPens;
    vector<int> distribution;
    // Unrestricted Distribution
    cout << "Enter the Number of pens (n): ";
    cin >> n;
    cout << "Enter the Number of people (k): ";
    cin >> k;
    cout << "\n--- Unrestricted Distribution ---\n";
    int unrestrictedWays = countWaysUnrestricted(n, k, distribution);
    cout << "Total ways (Unrestricted): " << unrestrictedWays << endl;
    // At Least One Pen per Person
    cout << "\n--- At Least One Pen per Person ---\n";
    if (n >= k) {
        int atLeastOneWays = countWaysAtLeastOne(n, k, distribution);
        cout << "Total ways (At Least One Pen): " << atLeastOneWays << endl;
    } else {
        cout << "Not enough pens for each person to get at least one.\n";
    }
    // At Most One Pen per Person
    cout << "\n--- At Most One Pen per Person ---\n";
    if (n <= k) {
        int atMostOneWays = countWaysAtMostOne(n, k, distribution);
        cout << "Total ways (At Most One Pen): " << atMostOneWays << endl;
    } else {
        cout << "Too many pens for each person to get at most one.\n";
    }
    // Equal Distribution
    cout << "\n--- Equal Distribution ---\n";
    int equalWays = countWaysEqualDistribution(n, k, distribution);
    if (equalWays > 0) {
        cout << "Total ways (Equal Distribution): " << equalWays << endl;
    } else {
        cout << "Cannot equally distribute pens among people.\n";
    }
    // Distribution with Maximum Limit per Person
    cout << "\n--- Distribution with Maximum Limit per Person ---\n";
    cout << "Enter the maximum Number of pens a person can receive: ";
    cin >> maxPens;
    int maxLimitWays = countWaysWithMaxLimit(n, k, maxPens, distribution);
    cout << "Total ways (Max Limit " << maxPens << " pens per person): " << maxLimitWays << endl;
    return 0;
}

Output:

Output


Enter the Number of pens (n): 10
Enter the Number of people (k): 3
--- Unrestricted Distribution ---
0 0 10 
0 1 9 
0 2 8 
0 3 7 
0 4 6 
0 5 5 
0 6 4 
0 7 3 
0 8 2 
0 9 1 
0 10 
1 0 9 
1 1 8 
1 2 7 
1 3 6 
1 4 5 
1 5 4 
1 6 3 
1 7 2 
1 8 1 
1 9 
2 0 8 
2 1 7 
2 2 6 
2 3 5 
2 4 4 
2 5 3 
2 6 2 
2 7 1 
2 8 
3 0 7 
3 1 6 
3 2 5 
3 3 4 
3 4 3 
3 5 2 
3 6 1 
3 7 
4 0 6 
4 1 5 
4 2 4 
4 3 3 
4 4 2 
4 5 1 
4 6 
5 0 5 
5 1 4 
5 2 3 
5 3 2 
5 4 1 
5 5 
6 0 4 
6 1 3 
6 2 2 
6 3 1 
6 4 
7 0 3 
7 1 2 
7 2 1 
7 3 
8 0 2 
8 1 1 
8 2 
9 0 1 
9 1 
10 
Total ways (Unrestricted): 66
--- At Least One Pen per Person ---
1 1 8 
1 2 7 
1 3 6 
1 4 5 
1 5 4 
1 6 3 
1 7 2 
1 8 1 
2 1 7 
2 2 6 
2 3 5 
2 4 4 
2 5 3 
2 6 2 
2 7 1 
3 1 6 
3 2 5 
3 3 4 
3 4 3 
3 5 2 
3 6 1 
4 1 5 
4 2 4 
4 3 3 
4 4 2 
4 5 1 
5 1 4 
5 2 3 
5 3 2 
5 4 1 
6 1 3 
6 2 2 
6 3 1 
7 1 2 
7 2 1 
8 1 1 
Total ways (At Least One Pen): 36
--- At Most One Pen per Person ---
Too many pens for each person to get at most one.
--- Equal Distribution ---
Cannot equally distribute pens among people.
--- Distribution with Maximum Limit per Person ---
Enter the maximum Number of pens a person can receive: 1
Total ways (Max Limit 1 pens per person): 0

Explanation:

The code gives a brute force solution to distribute n pens out of (k) people for different distribution rules. Each helper function solves a different variant of the problem using recursion and backtracking:

✅ countWaysUnrestricted: Sells pens without restrictions. It explores all of them recursively, which allocates pens from 0 to n for each person.
✅ countWaysAtLeastOne: Make sure everyone gets at least one pen. Anyone gets one pen at least, and the rest is distributed, so we get no more than zero pens for anyone.
✅ countWaysAtMostOne: Constrained by the total number of pens up to just n, each person can be limited to no more than one pen, therefore ensuring (k) is larger than or equal to n.
✅ countWaysEqualDistribution: People get equal parts of pens (if possible, but n divided by k). It outputs that no valid configuration exists if no equal distribution is possible. Otherwise, it will equal distribution.
✅ countWaysWithMaxLimit: It limits how many pens a person can have. This limit restricts allocation to this limit, decreasing the number of configurations.

Complexity Analysis:

Time Complexity

Unrestricted Distribution (countWaysUnrestricted):

✅ The function attempts to distribute n pens among k people in every possible way.
✅ It was made for each person to see how many pens (0 to n inclusive) it gives each person and how many choices each of the k people has (O(n)).
✅ Overall, it takes O(n k) time complexity.
✅ The function explores all possible combinations, which is exponentially complex. For large values of n and k, it becomes impractical.

At Least One Pen per Person (countWaysAtLeastOne):

✅ Here, the constraint reduces the problem size, so each person should receive at least one pen.
✅ We reduced the problem to n−k pens given to k people (in the beginning, each person got a pen).
✅ It has the same time complexity as O(n-k). It is a little better than the unrestricted Case, but it becomes very bad with large n and k.

At Most One Pen per Person (countWaysAtMostOne):

✅ The only way this variant works is that people can only get 0 or 1 pen each.
✅ We determine the number of valid configurations by choosing n of k (i.e., the binomial coefficient (kn)). The worst-case behavior is O(2𝑘 ) in time, where it takes as much time because it will explore every possible 'person who can receive pens' subset.
✅ It takes O(k) time complexity because dividing our pens and printing the result is all we have to do.

With Maximum Limit (countWaysWithMaxLimit):

✅ It works like the unrestricted case, except each person can get up to maxPens pens. It is of complexity O(min) to reduce the number of choices for each person.

Space Complexity

Space Complexity for All Functions:

✅ In order to store the current configuration, all functions use a vector (Distribution) of size k. The space complexity is O(k).
✅ The auxiliary space used in the recursive call stack can also reach a depth of k, so the total auxiliary space is O(k).

Approach-2: Dynamic programming

Dynamic Programming (DP) can provide us with a more efficient solution. The DP approach solves the problem in re-foldings, which reduces the problem into small subproblems and stores the results of these subproblems to avoid redundant computation. For instance, we employ the Stars and Bars method in the unrestricted Distribution, where the goal is to partition n identical items into k bins. DP helps to optimize this process, dramatically reducing time complexity. We can solve the problem in a reasonable time frame by using this method in larger input sizes.

Example:

Let us take an example to illustrate the Pen Distributing Problem in C++ using dynamix programming.

Example


#include <iostream>
#include <vector>
using namespace std;
//Function for unrestricted Distribution (Stars and Bars)
int countWaysUnrestrictedDP(int n, int k) {
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    // Base case: 1 way to distribute 0 pens to 0 people
    dp[0][0] = 1;
    // DP to fill the table
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j <= n; ++j) {
            //Case where the current person receives 0 pens
            dp[i][j] = dp[i-1][j];
            //Case where the current person receives 1 or more pens
            if (j > 0) {
                dp[i][j] += dp[i][j-1];
            }
        }
    }
    return dp[k][n];  // Number of ways to distribute n pens to k people
}
//Function for distributing pens where each person gets at least one pen
int countWaysAtLeastOneDP(int n, int k) {
    // First, we allocate 1 pen to each person
    if (n < k) return 0;  // Not enough pens to give at least 1 pen to each person
    // Now distribute the remaining n - k pens freely among k people
    return countWaysUnrestrictedDP(n - k, k);  // Now distribute the remaining n - k pens
}

//Function for distributing pens with at most one pen per person
int countWaysAtMostOne(int n, int k) {
    if (n > k) return 0;  // Not enough people to give each pen to a different person
    // Calculate binomial coefficient C(k, n)
    long long result = 1;
    for (int i = 0; i < n; ++i) {
        result *= (k - i);
        result /= (i + 1);
    }
    return result;
}
//Function for equal Distribution of pens
int countWaysEqualDistribution(int n, int k) {
    // Equal Distribution is only possible if n is divisible by k
    if (n % k != 0) return 0;
    // All people receive exactly n / k pens
    return 1;  // There is only 1 way to equally distribute pens
}
//Function for distributing pens with a maximum limit per person
int countWaysWithMaxLimit(int n, int k, int maxPens) {
    // DP approach to distributing n pens among k people with a max limit per person
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    // Base case: 1 way to distribute 0 pens to 0 people
    dp[0][0] = 1;
    // Fill the DP table
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j <= n; ++j) {
            //Case where the current person receives 0 pens
            dp[i][j] = dp[i-1][j];
            //Case where the current person receives from 1 to maxPens pens
            for (int x = 1; x <= maxPens && x <= j; ++x) {
                dp[i][j] += dp[i-1][j-x];
            }
        }
    }
    return dp[k][n];  //Number of ways to distribute n pens to k people with max limit
}
int main() {
    int n, k, maxPens;
    // Taking input for Number of pens and Number of people
    cout << "Enter the Number of pens (n): ";
    cin >> n;
    cout << "Enter the Number of people (k): ";
    cin >> k;
    // Unrestricted Distribution
    cout << "\n--- Unrestricted Distribution (DP) ---\n";
    int unrestrictedWays = countWaysUnrestrictedDP(n, k);
    cout << "Total ways (Unrestricted): " << unrestrictedWays << endl;
    // At Least One Pen per Person
    cout << "\n--- At Least One Pen per Person (DP) ---\n";
    int atLeastOneWays = countWaysAtLeastOneDP(n, k);
    cout << "Total ways (At Least One Pen): " << atLeastOneWays << endl;
    // At Most One Pen per Person
    cout << "\n--- At Most One Pen per Person (Combination) ---\n";
    int atMostOneWays = countWaysAtMostOne(n, k);
    cout << "Total ways (At Most One Pen): " << atMostOneWays << endl;
    // Equal Distribution
    cout << "\n--- Equal Distribution (DP) ---\n";
    int equalWays = countWaysEqualDistribution(n, k);
    cout << "Total ways (Equal Distribution): " << equalWays << endl;
    // Distributing Pens with Maximum Limit per Person
    cout << "\nEnter the maximum Number of pens a person can receive: ";
    cin >> maxPens;
    cout << "\n--- Distribution with Maximum Limit per Person (DP) ---\n";
    int maxLimitWays = countWaysWithMaxLimit(n, k, maxPens);
    cout << "Total ways (Max Limit): " << maxLimitWays << endl;
    return 0;
}

Output:

Output


Enter the Number of pens (n): 10
Enter the Number of people (k): 3
--- Unrestricted Distribution (DP) ---
Total ways (Unrestricted): 66
--- At Least One Pen per Person (DP) ---
Total ways (At Least One Pen): 36
--- At Most One Pen per Person (Combination) ---
Total ways (At Most One Pen): 0
--- Equal Distribution (DP) ---
Total ways (Equal Distribution): 0
Enter the maximum Number of pens a person can receive: 1
--- Distribution with Maximum Limit per Person (DP) ---
Total ways (Max Limit): 0

Explanation:

countWaysUnrestrictedDP:

✅ This function handles an unrestricted distribution of n pens among k people.
✅ We use a DP table dpi, where the Number of people is i and the Number of pens is j. Our base case is dp0 = 1, which means there is one way to distribute 0 pens to 0 people.
✅ A recurrence relation dpi = dpi-1 + dpi considers cases in which the current guy gets 0 pens or at least 1. Secondly, the total Number of ways to distribute n pens out to k people is stored in the result dpk.

countWaysAtLeastOneDP:

✅ The case in which each person has to get at least one pen is solved by this function. We reduced the problem by distributing the remaining n - k pens freely among k people, with each person allocated the first pen at first. After that, we use countWaysUnrestrictedDP function to append the ways by calling the function so that everyone gets at least one initial pen.

countWaysAtMostOne:

✅ If one person can be given no more than one pen, this function takes care of this case. We reduce the problem by selecting distinct people out of the people available. The solution to this can be done with combinations, which represents the number of ways to select n people out of k as binomial coefficient C(k,n).
✅ The function computes it iteratively.

countWaysEqualDistribution:

✅ This function is built to take care of the Distribution of equal pens. It only be possible if n /k is an integer, i.e. n%k==0. If the condition holds, there is exactly one way to distribute the pens equally: every person gets n/k pens.

countWaysWithMaxLimit:

✅ This function was made to solve the problem of distributing pens, with a limitation on the Number of pens each person gets.
✅ Given this, the function uses a DP table dpi, where i stands for the Number of people and j refers to the Number of pens used. The recurrence is for a person receiving 0 to maxPens pens, with an inner loop for the different numbers of pens a person might receive.

Complexity Analysis:

Time Complexity

Unrestricted Distribution (countWaysUnrestrictedDP):

It is so because we want to fill a DP table of size (k+1)×(n+1), which is calculated based on the values in the previous one. We compute, for each person (between 1 and k), the Number of ways to distribute up to n pens using a simple recurrence relation. The time complexity is thus O(k⋅n).

At Least One Pen per Person (countWaysAtLeastOneDP):

We first allocate 1 pen to every person, and n−k pens left. After that, the problem is reduced to the unrestricted distribution of all the rest of the pens, and the countWaysUnrestrictedDP function is used to compute that. The worst-case time complexity of this step is O(k⋅(n - k)) because we are doing a DP calculation for these remaining pens.

With Maximum Limit per Person (countWaysWithMaxLimit):

We take into consideration that all the people can get from 0 to maxPens pens to fill out the DP table. This results in three nested loops: two for people, two for pens, and 1 inner loop for the maximum number of people who can give pens. Consequently, the time complexity is O(k ⋅n⋅maxPens).

Space Complexity:

Unrestricted Distribution (countWaysUnrestrictedDP):

The DP table is a (k+1)×(n+1) 2D array , in which each entry stores the number of ways we can distribute j pens to i people. It directly leads to a space complexity of O(k⋅n).k is the number of people, and n is the Number of pens.

At Least One Pen per Person (countWaysAtLeastOneDP):

The space complexity is thus O(k⋅n). The function makes use of the countWaysUnrestrictedDP function that uses a DP table to compute the number of ways to distil the remaining n - k pens once one pen has been given to each person.

At Most One Pen per Person (countWaysAtMostOne):

This function computes binomial coefficient C(k,n) iteratively with constant use of variables in the function. As a result, the constant space complexity O(1).

With Maximum Limit per Person (countWaysWithMaxLimit):

In this function, the DP table is similar to what we have in the unrestricted distribution case, with dimensions (k+1)×(n+1), so the space complexity is O(k⋅n) where k is the number of people and n is the number of pens.

Introduction:

Approach-1: Brute Force Method

Example:

Explanation:

Complexity Analysis:

Approach-2: Dynamic programming

Example:

Explanation:

Complexity Analysis:

Input Required