# Distribute Candies Among Children II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/distribute-candies-among-children-ii)
Canonical: https://scaleengineer.com/dsa/problems/distribute-candies-among-children-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik), [ZS Associates](https://scaleengineer.com/companies/zs-associates)
---
## Problem
You are given two positive integers `n` and `limit`.

Return _the **total number** of ways to distribute_ `n` _candies among_ `3` _children such that no child gets more than_ `limit` _candies._

**Example 1:**

**Input:** n = 5, limit = 2
**Output:** 3
**Explanation:** There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

**Example 2:**

**Input:** n = 3, limit = 3
**Output:** 10
**Explanation:** There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

**Constraints:**

* `1 <= n <= 106`
* `1 <= limit <= 106`

# Approaches
## Brute-Force with Nested Loops
This approach involves iterating through all possible combinations of candies for the first two children and then checking if the remaining candies for the third child satisfy the given constraints.
**Time:** O(limit^2). The two nested loops each run up to `limit + 1` times in the worst case. For the given constraints (`limit` up to 10^6), this is too slow and will result in a Time Limit Exceeded error. · **Space:** O(1). We only use a constant amount of extra space for variables.
**Pros:** Very simple to understand and implement.; It's a direct translation of the problem's conditions into code.
**Cons:** Highly inefficient for large values of `limit`.; Fails to pass within the time limits for the given constraints.
### Explanation
We can solve this problem by systematically checking every possible distribution.
We use two nested loops. The outer loop iterates through the number of candies for the first child, `c1`, from 0 up to `limit`. The inner loop iterates through the number of candies for the second child, `c2`, from 0 up to `limit`.
For each pair `(c1, c2)`, we calculate the number of candies the third child would get: `c3 = n - c1 - c2`.
We then check if this distribution is valid. A distribution is valid if:
1. The total number of candies is `n` (which is true by our calculation of `c3`).
2. Each child gets a non-negative number of candies (`c1 >= 0`, `c2 >= 0`, `c3 >= 0`).
3. No child gets more than `limit` candies (`c1 <= limit`, `c2 <= limit`, `c3 <= limit`).
The loop bounds already ensure `0 <= c1 <= limit` and `0 <= c2 <= limit`. So, we only need to check if `0 <= c3 <= limit`.
If the distribution is valid, we increment a counter. After checking all combinations, the counter will hold the total number of valid ways.

```java
class Solution {
    public long distributeCandies(int n, int limit) {
        long count = 0;
        for (int i = 0; i <= limit; i++) {
            for (int j = 0; j <= limit; j++) {
                if (i + j > n) {
                    // Optimization: if sum of first two is already > n,
                    // no need to continue inner loop
                    break; 
                }
                int k = n - i - j;
                if (k >= 0 && k <= limit) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate `c1` from 0 to `limit`.
-   Iterate `c2` from 0 to `limit`.
-     Calculate `c3 = n - c1 - c2`.
-     If `c3 >= 0` and `c3 <= limit`, increment `count`.
- Return `count`.

## Optimized Iteration with a Single Loop
This approach improves upon the brute-force method by reducing the number of loops from two to one. We iterate through the possibilities for the first child and then mathematically calculate the number of valid ways for the other two children.
**Time:** O(min(n, limit)). The single loop runs `min(n, limit) + 1` times. This is a significant improvement but can still be too slow if both `n` and `limit` are large (e.g., 10^6). · **Space:** O(1). Only a constant amount of extra space is used.
**Pros:** Much faster than the O(limit^2) brute-force approach.; Still relatively intuitive.
**Cons:** Not efficient enough to pass for the largest possible inputs where `min(n, limit)` is close to 10^6.
### Explanation
Instead of iterating through possibilities for both the first and second child, we can fix the number of candies for one child, say `c1`, and then determine the number of ways to distribute the remaining candies between the other two.
Let the first child receive `c1` candies, where `0 <= c1 <= min(n, limit)`. The remaining `n - c1` candies must be distributed between the second and third child: `c2 + c3 = n - c1`.
We also have the constraints `0 <= c2 <= limit` and `0 <= c3 <= limit`.
Let `rem_n = n - c1`. We need to find the number of solutions to `c2 + c3 = rem_n` with `0 <= c2, c3 <= limit`.
From `c3 = rem_n - c2`, the constraint `0 <= c3 <= limit` becomes `0 <= rem_n - c2 <= limit`.
This gives two inequalities for `c2`:
1. `rem_n - c2 >= 0`  => `c2 <= rem_n`
2. `rem_n - c2 <= limit` => `c2 >= rem_n - limit`
Combining all constraints on `c2` (`0 <= c2 <= limit`, `c2 <= rem_n`, `c2 >= rem_n - limit`), we get the valid range for `c2`: `max(0, rem_n - limit) <= c2 <= min(limit, rem_n)`.
The number of integer solutions for `c2` in this range is `min(limit, rem_n) - max(0, rem_n - limit) + 1`.
We iterate `c1` from 0 to `min(n, limit)`, calculate this quantity for each `c1`, and sum them up to get the total count.

```java
class Solution {
    public long distributeCandies(int n, int limit) {
        long count = 0;
        for (int i = 0; i <= Math.min(n, limit); i++) {
            int remaining_n = n - i;
            // We need to find solutions for c2 + c3 = remaining_n
            // where 0 <= c2, c3 <= limit
            
            // From c3 = remaining_n - c2, we have 0 <= remaining_n - c2 <= limit
            // This gives: remaining_n - limit <= c2 <= remaining_n
            
            // Combining with 0 <= c2 <= limit, we get:
            // max(0, remaining_n - limit) <= c2 <= min(limit, remaining_n)
            
            int min_c2 = Math.max(0, remaining_n - limit);
            int max_c2 = Math.min(limit, remaining_n);
            
            if (max_c2 >= min_c2) {
                count += (max_c2 - min_c2 + 1);
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate `c1` from 0 to `min(n, limit)`.
-   Calculate the remaining candies: `rem_n = n - c1`.
-   Determine the lower bound for `c2`: `lower_bound = max(0, rem_n - limit)`.
-   Determine the upper bound for `c2`: `upper_bound = min(limit, rem_n)`.
-   If `upper_bound >= lower_bound`, add `(upper_bound - lower_bound + 1)` to `count`.
- Return `count`.

## Combinatorics with Inclusion-Exclusion Principle
This is the most efficient approach, solving the problem in constant time using mathematical formulas. It first calculates the total number of ways to distribute `n` candies without any upper limit and then uses the Principle of Inclusion-Exclusion to subtract the invalid distributions where one or more children receive more than `limit` candies.
**Time:** O(1). The solution involves a constant number of arithmetic calculations, regardless of the input size. · **Space:** O(1). No extra space proportional to the input size is used.
**Pros:** Extremely efficient, providing an instant solution even for the largest constraints.; Mathematically elegant.
**Cons:** Requires knowledge of combinatorics (stars and bars) and the Principle of Inclusion-Exclusion, making it less intuitive than iterative approaches.
### Explanation
The problem is equivalent to finding the number of non-negative integer solutions to `x1 + x2 + x3 = n` subject to `x1, x2, x3 <= limit`.
**Step 1: Ignore the upper limit.** The number of non-negative solutions to `x1 + x2 + x3 = n` can be found using stars and bars. The formula is `C(n + k - 1, k - 1)` where `k=3`. This gives `C(n + 2, 2) = (n + 2) * (n + 1) / 2`. Let's create a helper function `ways(k)` for this calculation, which returns 0 if `k < 0`.
**Step 2: Apply Inclusion-Exclusion.** We need to subtract the cases where the `limit` constraint is violated.
- Let `P1` be the property that `x1 > limit`, `P2` that `x2 > limit`, and `P3` that `x3 > limit`. We want to find the total ways minus the ways that have at least one of these properties.
- **Subtract cases where one child exceeds the limit:** The number of ways where `x1 > limit` (i.e., `x1 >= limit + 1`) is found by pre-allocating `limit + 1` candies to child 1 and distributing the rest: `x1' + x2 + x3 = n - (limit + 1)`. The number of solutions is `ways(n - limit - 1)`. By symmetry, this is the same for `x2` and `x3`. So we subtract `3 * ways(n - limit - 1)`.
- **Add back cases where two children exceed the limit:** We subtracted cases where two children exceed the limit twice. We need to add them back once. The number of ways where `x1 > limit` and `x2 > limit` is `ways(n - 2 * (limit + 1))`. By symmetry, there are 3 such pairs. So we add back `3 * ways(n - 2 * (limit + 1))`.
- **Subtract cases where three children exceed the limit:** These were subtracted three times and added back three times, so they haven't been accounted for correctly. We need to subtract them once. The number of ways is `ways(n - 3 * (limit + 1))`.
**Final Formula:** The total number of valid ways is `ways(n) - 3 * ways(n - limit - 1) + 3 * ways(n - 2 * (limit + 1)) - ways(n - 3 * (limit + 1))`.

```java
class Solution {
    public long distributeCandies(int n, int limit) {
        // Total ways to distribute n candies to 3 children without limit
        long totalWays = ways(n);
        
        // Using Inclusion-Exclusion Principle
        // Let A, B, C be the sets of distributions where child 1, 2, 3
        // get more than 'limit' candies respectively.
        // We want to find |U| - |A U B U C|
        // |A U B U C| = |A|+|B|+|C| - (|A n B|+|A n C|+|B n C|) + |A n B n C|
        
        // Case 1: At least one child gets more than 'limit' candies.
        long oneExceeds = 3 * ways(n - limit - 1);
        
        // Case 2: At least two children get more than 'limit' candies.
        long twoExceeds = 3 * ways(n - 2 * (limit + 1));
        
        // Case 3: All three children get more than 'limit' candies.
        long threeExceeds = ways(n - 3 * (limit + 1));
        
        return totalWays - oneExceeds + twoExceeds - threeExceeds;
    }

    private long ways(int k) {
        if (k < 0) {
            return 0;
        }
        // C(k+2, 2) = (k+2)*(k+1)/2
        // Using long to prevent overflow before division
        return (long)(k + 2) * (k + 1) / 2;
    }
}
```
### Algorithm
- Define a helper function `ways(k)`:
    - If `k < 0`, return 0.
    - Otherwise, return `(long)(k + 2) * (k + 1) / 2`.
- Calculate `total_ways = ways(n)`.
- Calculate `ways_one_exceeds = ways(n - limit - 1)`.
- Calculate `ways_two_exceeds = ways(n - 2 * (limit + 1))`.
- Calculate `ways_three_exceeds = ways(n - 3 * (limit + 1))`.
- Apply the Inclusion-Exclusion formula: `result = total_ways - 3 * ways_one_exceeds + 3 * ways_two_exceeds - ways_three_exceeds`.
- Return `result`.

# Solutions
### Java

```java
class Solution {
public
  long distributeCandies(int n, int limit) {
    if (n > 3 * limit) {
      return 0;
    }
    long ans = comb2(n + 2);
    if (n > limit) {
      ans -= 3 * comb2(n - limit + 1);
    }
    if (n - 2 >= 2 * limit) {
      ans += 3 * comb2(n - 2 * limit);
    }
    return ans;
  }
private
  long comb2(int n) { return 1L * n * (n - 1) / 2; }
}

```

### CPP

```cpp
class Solution {
public:
  long long distributeCandies(int n, int limit) {
    auto comb2 = [](int n) { return 1LL * n * (n - 1) / 2; };
    if (n > 3 * limit) {
      return 0;
    }
    long long ans = comb2(n + 2);
    if (n > limit) {
      ans -= 3 * comb2(n - limit + 1);
    }
    if (n - 2 >= 2 * limit) {
      ans += 3 * comb2(n - 2 * limit);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def distributeCandies(self, n: int, limit: int) -> int: if n > 3 * limit: return 0 ans = comb(n + 2, 2) if n > limit: ans -= 3 * comb(n - limit + 1, 2) if n - 2 >= 2 * limit: ans += 3 * comb(n - 2 * limit, 2) return ans

```