Distribute Candies Among Children II

Distribute Candies Among Children II

What is this problem about?

This is the "Medium" version of the previous problem. In the Distribute Candies Among Children II interview question, the number of candies $n$ can be up to $10^6$. You still need to distribute $n$ candies among 3 children with a per-child limit. Because $n$ is large, an $O(n^2)$ nested loop will be too slow. You need an $O(1)$ or $O(limit)$ solution.

Why is this asked in interviews?

Companies like Meta and Google ask this to see if you can apply Combinatorics to solve efficiency bottlenecks. It evaluations your understanding of the Stars and Bars interview pattern and the Principle of Inclusion-Exclusion (PIE). It tests whether you can move from a "coding" mindset to a "mathematical modeling" mindset.

Algorithmic pattern used

This problem is solved using the Stars and Bars formula combined with Inclusion-Exclusion.

1. Total ways (no limit): The number of ways to distribute $n$ candies to 3 children is $\binom{n+3-1}{3-1} = \binom{n+2}{2} = \frac{(n+2)(n+1)}{2}$.
2. Subtract Invalid Cases: Use Inclusion-Exclusion to subtract cases where one, two, or all three children exceed the limit.
   • If one child gets at least limit + 1 candies, you give them those candies first and then distribute the remaining $n - (limit + 1)$ candies freely.
3. Formula: Total - 3 * (at least one exceeds) + 3 * (at least two exceed) - 1 * (all three exceed).

Example explanation

$n=5, limit=2$.

1. Total: $\binom{5+2}{2} = \binom{7}{2} = 21$.
2. Exceed 1: Give one child 3 candies. Remainder $5-3=2$. $\binom{2+2}{2} = 6$. Since there are 3 children, $3 \times 6 = 18$.
3. Exceed 2: Give two children 3 candies each. Sum = 6. Impossible since $6 > n$. Result: $21 - 18 = 3$. (The ways are (2,2,1), (2,1,2), (1,2,2)).

Common mistakes candidates make

• Negative Combinations: Trying to calculate $\binom{n}{k}$ when $n < k$. You must return 0 in these cases.
• PIE Errors: Forgetting to add back the double-counted intersections in the Inclusion-Exclusion formula.
• Integer Overflow: Not using long integers for the intermediate product $(n+2)(n+1)$.

Interview preparation tip

Learn the "Stars and Bars" method for distributing identical items into distinct bins. It is a frequent Combinatorics interview pattern that turns counting problems into simple $O(1)$ formula evaluations.