Distribute Candies Among Children I

Difficulty: Easy | Acceptance: 76.40% | Paid: No Topics: Math, Combinatorics, Enumeration

You are given two positive integers n and limit.

Distribute n candies among 3 children such that:

Each child gets at least one candy. No child gets more than limit candies. Return the number of ways to distribute the candies.

Examples
Constraints
Brute Force Enumeration
Mathematical Formula (Inclusion-Exclusion)

Examples

Example 1: Input: n = 5, limit = 2 Output: 3 Explanation: There are 3 ways to distribute the 5 candies such that each child gets at least one candy and no child gets more than 2 candies: (1,2,2), (2,1,2), (2,2,1).

Example 2: Input: n = 3, limit = 3 Output: 1 Explanation: There is only 1 way to distribute the 3 candies: (1,1,1).

Constraints

- 1 <= n <= 50
- 1 <= limit <= 50

Brute Force Enumeration

Intuition Iterate through all possible distributions of candies to the first two children and check if the third child gets a valid amount.

Steps

Iterate through possible candies for child 1 (1 to min(limit, n-2))
For each value, iterate through possible candies for child 2 (1 to min(limit, n-child1-1))
Calculate candies for child 3 and check if it’s valid (1 to limit)
Count all valid distributions

python

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        count = 0
        for a in range(1, min(limit, n - 2) + 1):
            for b in range(1, min(limit, n - a - 1) + 1):
                c = n - a - b
                if 1 &lt;= c &lt;= limit:
                    count += 1
        return count

Complexity

Time: O(limit²)
Space: O(1)
Notes: Simple and intuitive, works well for small constraints

Mathematical Formula (Inclusion-Exclusion)

Intuition Use combinatorics with the inclusion-exclusion principle to count valid distributions without enumeration.

Steps

Transform the problem: let yi = xi - 1, so 0 <= yi <= limit - 1 and y1 + y2 + y3 = n - 3
Count total solutions without upper bound using stars and bars: C(n-1, 2)
Subtract cases where at least one child exceeds limit using inclusion-exclusion
Formula: C(n-1, 2) - 3C(n-1-limit, 2) + 3C(n-1-2limit, 2) - C(n-1-3limit, 2)

python

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        def C(n, k):
            if n &lt; 0 or n &lt; k:
                return 0
            if k == 0 or k == n:
                return 1
            if k == 1:
                return n
            return n * (n - 1) // 2
        
        return C(n - 1, 2) - 3 * C(n - 1 - limit, 2) + 3 * C(n - 1 - 2 * limit, 2) - C(n - 1 - 3 * limit, 2)

Complexity

Time: O(1)
Space: O(1)
Notes: Optimal solution using combinatorial mathematics