Distribute Candies Among Children III - Solution & Explanation

Problem Overview: You are given n candies and three children. Each child can receive at most limit candies. The task is to count how many valid distributions exist such that the total candies distributed equals n while no child exceeds the limit.

This is a classic counting problem. Without restrictions, distributing n identical items across three variables (a + b + c = n) can be solved using the stars and bars formula. The challenge comes from the upper bound constraint (a, b, c ≤ limit). Handling that constraint efficiently leads to a combinatorics-based solution.

Approach 1: Enumerate Valid Pairs (Brute Force Iteration) (Time: O(limit^2), Space: O(1))

Iterate over the candies given to the first two children. For each pair (a, b), compute c = n - a - b. The distribution is valid if 0 ≤ a ≤ limit, 0 ≤ b ≤ limit, and 0 ≤ c ≤ limit. This brute force approach checks every feasible pair and increments a counter when the third child also satisfies the constraint. It works because the number of children is fixed at three, but the nested iteration makes it quadratic in the worst case.

This approach is straightforward and useful for validating logic during development. However, it becomes inefficient when limit is large.

Approach 2: Combinatorial Mathematics + Principle of Inclusion-Exclusion (Time: O(1), Space: O(1))

First ignore the upper bound. The number of ways to distribute n candies among three children is given by the stars and bars formula: C(n + 2, 2). This counts all non‑negative integer solutions to a + b + c = n.

Next remove distributions where at least one child exceeds the limit. If child a gets more than limit, substitute a' = a - (limit + 1). The equation becomes a' + b + c = n - (limit + 1). The number of such solutions is C(n - limit + 1, 2). Apply the same logic for each child.

However, subtracting these individually double‑counts cases where two children exceed the limit. The combinatorics technique called the principle of inclusion‑exclusion fixes this by adding back intersections of invalid sets. With only three variables, the formula remains small and can be computed with a few combination calculations.

This turns the entire counting process into constant time arithmetic. No loops are required, and the memory footprint stays constant. Problems involving bounded integer solutions often reduce to this exact pattern using mathematical counting.

Recommended for interviews: The combinatorial + inclusion‑exclusion solution is what interviewers expect. It shows that you recognize the equation a + b + c = n as a stars‑and‑bars problem and know how to enforce upper bounds mathematically. Mentioning the brute force iteration first demonstrates understanding, but deriving the O(1) combinatorial formula demonstrates stronger problem‑solving skills.