🍬Beginner-Friendly Guide to Solving "Distribute Candies Among Children II" | LeetCode 2929 Explained (C++ | JavaScript | Python)

Distributing candies among children sounds simple, right? But what if there’s a limit on how many candies each child can get? Let’s break down this classic combinatorial problem and solve it efficiently!

Problem Statement

You are given two positive integers:

• n = total candies
• limit = maximum candies any child can receive

Goal: Find the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

Example

• Input: n = 5, limit = 2
• Output: 3
• Explanation: Valid distributions are (1, 2, 2), (2, 1, 2), and (2, 2, 1).

Step 1: Understand the Basics (Stars and Bars) ⭐✨

Without any limit, the problem reduces to distributing n identical candies into 3 children (bins), which can be done in:

Total ways = C(n + 3 - 1, 3 - 1) = C(n + 2, 2)

Here, C(a, b) is the binomial coefficient "a choose b".

This formula comes from the Stars and Bars theorem:
Imagine n stars (candies) separated by 2 bars (dividers) that partition candies between the 3 children.

Step 2: Add the Limit Constraint Using Inclusion-Exclusion Principle 🔍

We must exclude all distributions where any child has more than limit candies.

Breakdown:

• Let’s denote limit + 1 as L for simplicity.

• Define sets:

  • A: Distributions where child 1 gets ≥ L candies
  • B: Distributions where child 2 gets ≥ L candies
  • C: Distributions where child 3 gets ≥ L candies

Our task: Count all distributions not in A ∪ B ∪ C.

Step 3: Use Inclusion-Exclusion Formula 🧮

We start with total distributions (no limits) and subtract distributions where the limit is exceeded:

Answer = Total - |A ∪ B ∪ C|

By Inclusion-Exclusion:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|

Calculate Each Term:

• Total (no limits):

  T = C(n + 2, 2)

• Number of distributions where one child exceeds the limit:

For child 1 exceeding limit, redefine candies:

  a' = a - L ≥ 0

Remaining candies to distribute:

  n' = n - L

Number of such distributions for one child:

  A = C(n' + 2, 2) = C(n - L + 2, 2)

Since this applies to any of the 3 children:

  |A| + |B| + |C| = 3 × A

• Distributions where two children exceed the limit:

Similar reasoning:

  n'' = n - 2 × L

Number of such distributions:

  B = C(n'' + 2, 2) = C(n - 2 × L + 2, 2)

Number of pairs of children = 3

  |A ∩ B| + |B ∩ C| + |A ∩ C| = 3 × B

• Distributions where all three children exceed the limit:

  n''' = n - 3 × L

Number of such distributions:

  C = C(n''' + 2, 2) = C(n - 3 × L + 2, 2)

Step 4: Final Formula

Putting it all together:

Answer = T - 3 × A + 3 × B - C

where:

T = C(n + 2, 2)
A = C(n - L + 2, 2)
B = C(n - 2 × L + 2, 2)
C = C(n - 3 × L + 2, 2)

Step 5: Efficient Implementation in Code 💻

Let’s implement this in C++, JavaScript and Python.

C++

#include <iostream>
using namespace std;

long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    long long res = 1;
    for (int i = 1; i <= k; ++i) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

long long distributeCandies(int n, int limit) {
    int L = limit + 1;
    long long T = comb(n + 2, 2);
    long long A = comb(n - L + 2, 2);
    long long B = comb(n - 2 * L + 2, 2);
    long long C = comb(n - 3 * L + 2, 2);

    return T - 3 * A + 3 * B - C;
}

int main() {
    cout << distributeCandies(5, 2) << endl;  // Output: 3
    cout << distributeCandies(3, 3) << endl;  // Output: 10
    return 0;
}

JavaScript

function comb(n, k) {
    if (k < 0 || k > n) return 0;
    let res = 1;
    for (let i = 1; i <= k; i++) {
        res *= (n - i + 1);
        res /= i;
    }
    return res;
}

function distributeCandies(n, limit) {
    const L = limit + 1;
    const T = comb(n + 2, 2);
    const A = comb(n - L + 2, 2);
    const B = comb(n - 2 * L + 2, 2);
    const C = comb(n - 3 * L + 2, 2);

    return T - 3 * A + 3 * B - C;
}

// Example:
console.log(distributeCandies(5, 2));  // Output: 3
console.log(distributeCandies(3, 3));  // Output: 10

Python

def comb(n, k):
    if k < 0 or k > n:
        return 0
    res = 1
    for i in range(1, k + 1):
        res *= (n - i + 1)
        res //= i
    return res

def distribute_candies(n, limit):
    L = limit + 1
    T = comb(n + 2, 2)
    A = comb(n - L + 2, 2)
    B = comb(n - 2 * L + 2, 2)
    C = comb(n - 3 * L + 2, 2)

    return T - 3 * A + 3 * B - C

# Example:
print(distribute_candies(5, 2))  # Output: 3
print(distribute_candies(3, 3))  # Output: 10

Conclusion 🎉

This problem is a great example of combining combinatorics with algorithmic optimization. The brute-force approach would be too slow for large inputs, but using the stars and bars theorem and the inclusion-exclusion principle, we can solve it efficiently in constant time after computing binomial coefficients.

Final Thoughts 🎯

1. Using combinatorics and inclusion-exclusion allows for an O(1) time solution.

2. Brute-force is inefficient for large inputs but okay for small values.

3. This problem is a great example of applying mathematical thinking to optimize algorithms.

I hope this step-by-step explanation helps you understand how to tackle distribution problems with constraints. Feel free to share your thoughts or questions!