# Distribute Candies Among Children I
**Difficulty:** EASY
[External](https://leetcode.com/problems/distribute-candies-among-children-i)
Canonical: https://scaleengineer.com/dsa/problems/distribute-candies-among-children-i
**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)
---
## 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 <= 50`
* `1 <= limit <= 50`

# Approaches
## Brute-Force with Three Nested Loops
This approach iterates through all possible combinations of candies for the three children using three nested loops. For each combination, it checks if the total number of candies equals `n` and if each child's candy count is within the `limit`.
**Time:** O(limit^3). The three nested loops each run up to `limit + 1` times. For the given constraints (`limit <= 50`), this is feasible (approx. 51*51*51 operations). · **Space:** O(1). We only use a few variables to store the count and loop indices, so the space used is constant.
**Pros:** Very simple to understand and implement.; Guaranteed to be correct if implemented properly.
**Cons:** Inefficient for larger values of `limit`.; Performs many redundant calculations.
### Explanation
We can simulate the distribution process directly. Let the number of candies for the three children be `c1`, `c2`, and `c3`.

We can use three nested loops, each iterating from 0 to `limit`, representing the number of candies for each child. Inside the innermost loop, we check if the sum of candies is exactly `n`: `c1 + c2 + c3 == n`. The condition that each child gets at most `limit` candies is inherently handled by the loop bounds.

If the sum condition is met, we increment a counter. After checking all `(limit + 1)^3` combinations, the counter will hold the total number of valid distributions.

```java
class Solution {
    public int distributeCandies(int n, int limit) {
        int count = 0;
        for (int i = 0; i <= limit; i++) {
            for (int j = 0; j <= limit; j++) {
                for (int k = 0; k <= limit; k++) {
                    if (i + j + k == n) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a for-loop to iterate through the number of candies for the first child, `i`, from 0 to `limit`.
- Inside the first loop, use a nested for-loop for the second child, `j`, from 0 to `limit`.
- Inside the second loop, use another nested for-loop for the third child, `k`, from 0 to `limit`.
- In the innermost loop, check if the sum `i + j + k` equals `n`.
- If the sum is equal to `n`, increment the `count`.
- After the loops finish, return `count`.

## Optimized Brute-Force with Two Nested Loops
This approach improves upon the brute-force method by using only two nested loops. After choosing the number of candies for the first two children, the number for the third child is determined automatically. We then just need to check if this number is valid.
**Time:** O(limit^2). We have two nested loops, each running up to `limit + 1` times. This is a significant improvement over the O(limit^3) approach. · **Space:** O(1). Constant extra space is used for the counter and loop variables.
**Pros:** More efficient than the three-loop brute-force.; Still relatively easy to understand and implement.
**Cons:** Not the most optimal solution.; Can be further optimized for even better performance.
### Explanation
Instead of iterating through possibilities for all three children, we can iterate for the first two and calculate the required candies for the third. Let `c1` and `c2` be the candies for the first two children. The number of candies for the third child, `c3`, must be `n - c1 - c2` to satisfy the sum condition.

We use two nested loops to iterate `c1` from 0 to `limit` and `c2` from 0 to `limit`. For each pair `(c1, c2)`, we calculate `c3 = n - c1 - c2`. Then, we check if `c3` is a valid number of candies, which means it must satisfy `0 <= c3 <= limit`. If `c3` is valid, we increment our count of valid distributions.

This eliminates one level of looping, significantly improving performance from O(limit^3) to O(limit^2).

```java
class Solution {
    public int distributeCandies(int n, int limit) {
        int count = 0;
        for (int i = 0; i <= limit; i++) {
            for (int j = 0; j <= limit; j++) {
                int k = n - i - j;
                if (k >= 0 && k <= limit) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a for-loop to iterate through the number of candies for the first child, `i`, from 0 to `limit`.
- Inside the first loop, use a nested for-loop for the second child, `j`, from 0 to `limit`.
- Calculate the number of candies for the third child: `k = n - i - j`.
- Check if `k` is valid, i.e., `0 <= k <= limit`.
- If `k` is valid, increment the `count`.
- After the loops finish, return `count`.

## Combinatorics with Inclusion-Exclusion Principle
This is a purely mathematical approach that provides a constant-time solution. It uses the 'stars and bars' method to find the total number of ways to distribute `n` items into 3 bins without an upper limit, and then applies the Principle of Inclusion-Exclusion to subtract the cases where one or more children receive more than `limit` candies.
**Time:** O(1). The solution involves a fixed number of arithmetic calculations, regardless of the input values `n` and `limit`. · **Space:** O(1). Only a few variables are needed to store the intermediate and final results.
**Pros:** The most efficient solution with constant time complexity.; Elegant mathematical solution.
**Cons:** Requires knowledge of combinatorics and the Principle of Inclusion-Exclusion.; Less intuitive and harder to derive than iterative solutions.
### Explanation
The problem is equivalent to finding the number of non-negative integer solutions to `c1 + c2 + c3 = n` subject to `0 <= c_i <= limit`.

First, we ignore the upper bound (`limit`). The number of non-negative solutions to `c1 + c2 + c3 = n` is given by the stars and bars formula: `C(n + 3 - 1, 3 - 1) = C(n + 2, 2)`.

Next, we use the Principle of Inclusion-Exclusion to handle the `c_i <= limit` constraint. We subtract the cases where at least one child gets more than `limit` candies, add back the cases where at least two children get more than `limit`, and so on.

The final formula is: `Ways = C(n+2, 2) - 3 * C(n-limit+1, 2) + 3 * C(n-2*limit, 2) - C(n-3*limit-1, 2)`.

Here, `C(m, 2)` is the number of combinations 'm choose 2', which is `m * (m - 1) / 2` for `m >= 2` and 0 otherwise. This method directly calculates the result without any iteration.

```java
class Solution {
    public int distributeCandies(int n, int limit) {
        // Total ways to distribute n candies to 3 children without limit
        long totalWays = combinations2(n + 2);

        // Subtract cases where one child gets more than 'limit' candies
        // n' = n - (limit + 1)
        long oneChildExceeds = 3 * combinations2(n - limit - 1 + 2);

        // Add back cases where two children get more than 'limit' candies
        // n'' = n - 2 * (limit + 1)
        long twoChildrenExceed = 3 * combinations2(n - 2 * (limit + 1) + 2);

        // Subtract cases where three children get more than 'limit' candies
        // n''' = n - 3 * (limit + 1)
        long threeChildrenExceed = combinations2(n - 3 * (limit + 1) + 2);

        return (int) (totalWays - oneChildExceeds + twoChildrenExceed - threeChildrenExceed);
    }

    private long combinations2(int m) {
        if (m < 2) {
            return 0;
        }
        return (long) m * (m - 1) / 2;
    }
}
```
### Algorithm
- Define a helper function `combinations2(m)` that computes `C(m, 2)`.
- Calculate the total ways without an upper limit: `ways1 = combinations2(n + 2)`.
- Calculate the ways where at least one child violates the limit: `ways2 = 3 * combinations2(n - limit + 1)`.
- Calculate the ways where at least two children violate the limit: `ways3 = 3 * combinations2(n - 2 * limit)`.
- Calculate the ways where all three children violate the limit: `ways4 = combinations2(n - 3 * limit - 1)`.
- Apply the Principle of Inclusion-Exclusion: `result = ways1 - ways2 + ways3 - ways4`.
- Return the final `result`.

# Solutions
### Java

```java
class Solution {
public
  int 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 (int)ans;
  }
private
  long comb2(int n) { return 1L * n * (n - 1) / 2; }
}

```

### CPP

```cpp
class Solution {
public:
  int 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

```