1. Brute Force

Intuition

The most straightforward approach is to try every possible combination of candies for the three children. We iterate through all values for child A, child B, and child C (each from 0 to the limit), and count only those combinations where the total equals exactly n candies. While simple to understand, this method checks many invalid combinations.

Algorithm

1. Initialize a counter res to 0.
2. Use three nested loops to iterate through all possible candy amounts for each child (0 to limit).
3. For each combination (a, b, c), check if a + b + c == n.
4. If true, increment the counter.
5. Return the total count.

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(limit + 1):
            for b in range(limit + 1):
                for c in range(limit + 1):
                    if a + b + c == n:
                        res += 1
        return res

Time & Space Complexity

• Time complexity: $O(l ^ 3)$
• Space complexity: $O(1)$

Where $l$ is the given limit.

---

2. Better Approach

Intuition

We can reduce unnecessary iterations by fixing the first child's amount and only looping through valid values for the second child. Once we know how many candies child A and child B receive, child C's amount is determined: c = n - a - b. We simply check if this value is within the allowed limit.

Algorithm

1. Initialize a counter res to 0.
2. Loop through possible values for a from 0 to min(n, limit).
3. For each a, loop through possible values for b from 0 to min(n - a, limit).
4. Calculate c = n - a - b. If c <= limit, increment the counter.
5. Return the total count.

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(min(n, limit) + 1):
            for b in range(min(n - a, limit) + 1):
                if n - a - b <= limit:
                    res += 1
        return res

Time & Space Complexity

• Time complexity: $O(min(n, limit) ^ 2)$
• Space complexity: $O(1)$

---

3. Enumeration - I

Intuition

Instead of iterating through every value of b, we can directly compute the range of valid values. For a fixed a, child B can receive anywhere from b_min to b_max candies, where b_max = min(n - a, limit) and b_min = max(0, n - a - limit). The lower bound ensures child C does not exceed the limit. The number of valid b values is simply b_max - b_min + 1.

Algorithm

1. Initialize a counter res to 0.
2. Loop through possible values for a from 0 to min(n, limit).
3. For each a, compute b_max = min(n - a, limit) and b_min = max(0, n - a - limit).
4. If b_max >= b_min, add (b_max - b_min + 1) to the counter.
5. Return the total count.

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(min(n, limit) + 1):
            b_max = min(n - a, limit)
            b_min = max(0, n - a - limit)
            if b_max >= b_min:
                res += b_max - b_min + 1
        return res

Time & Space Complexity

• Time complexity: $O(min(n, limit))$
• Space complexity: $O(1)$

---

4. Enumeration - II

Intuition

This is a slight optimization of the previous approach. We add an early check: if the remaining candies n - a exceeds 2 * limit, it is impossible to distribute them between child B and child C (since each can hold at most limit). This allows us to skip invalid values of a entirely.

Algorithm

1. Initialize a counter res to 0.
2. Loop through possible values for a from 0 to min(n, limit).
3. Let rem = n - a. If rem > 2 * limit, skip this iteration.
4. Otherwise, compute the number of valid (b, c) pairs as min(rem, limit) - max(0, rem - limit) + 1.
5. Add this count to res.
6. Return the total count.

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        res = 0
        for a in range(min(n, limit) + 1):
            if n - a <= 2 * limit:
                res += min(n - a, limit) - max(0, n - a - limit) + 1
        return res

Time & Space Complexity

• Time complexity: $O(min(n, limit))$
• Space complexity: $O(1)$

---

5. Inclusion-Exclusion Principle

Intuition

We can solve this in constant time using combinatorics. The total number of ways to distribute n candies among 3 children (without the limit constraint) is C(n+2, 2). However, we need to subtract cases where at least one child exceeds the limit. Using the inclusion-exclusion principle, we subtract cases where one child exceeds the limit, add back cases where two children exceed it (since they were subtracted twice), and subtract cases where all three exceed it.

Algorithm

1. Define the binomial coefficient for choosing 2 from m+2 as (m+2)*(m+1)/2.
2. For j from 0 to 3, calculate m = n - j * (limit + 1).
3. If m < 0, skip this term.
4. Compute ways = (m+2)*(m+1)/2.
5. Apply alternating signs using the inclusion-exclusion pattern and multiply by C(3, j).
6. Sum all terms and return the result.

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        C3 = [1, 3, 3, 1]
        res = 0
        for j in range(4):
            m = n - j * (limit + 1)
            if m < 0:
                continue
            ways = (m + 2) * (m + 1) // 2
            sign = -1 if j % 2 else 1
            res += sign * C3[j] * ways
        return res

Time & Space Complexity

• Time complexity: $O(1)$
• Space complexity: $O(1)$