LeetCode 2922 Edge Cases: Candy Distribution

LeetCode 2922, “Distribute Candies Among Children II,� asks how many ways you can distribute n identical candies to 3 children so that each child gets between 0 and limit candies. The common edge cases involve n = 0, limit = 0, very large n relative to limit, and values that force the answer to zero; handling these correctly is the difference between a working solution and one that fails hidden tests.

Formula

The formula counts the number of non‑negative integer solutions to x + y + z = n with each variable ≤ limit. Start with the unbounded count C(n+2, 2) = (n+1)(n+2)/2, then subtract cases where one child exceeds the limit, add back cases where two children exceed it (inclusion‑exclusion). The final expression is:

Ways = (n+1)(n+2)/2 − 3·(n−limit)(n−limit+1)/2 + 3·(n−2·limit−1)(n−2·limit)/2

Each term is only counted when the subtracted quantity is positive; otherwise it contributes zero. The variables are: n (total candies, integer ≥ 0), limit (maximum candies per child, integer ≥ 0).

Worked Example

With the default values n = 5, limit = 3:

• Unbounded count: (5+1)(5+2)/2 = 21
• Subtract one child over limit: 3·(5−3)(5−3+1)/2 = 3·2·3/2 = 9
• Add back two children over limit: 3·(5−6−1)(5−6)/2 → the term is negative, so it becomes 0.
• Total: 21 − 9 = 12

The calculator returns 12, matching the manual count.

Edge Case: n = 0

When there are no candies, the only valid distribution is (0,0,0) regardless of limit. The formula gives (0+1)(0+2)/2 = 1 and all subtraction terms are zero, so the answer is 1. A common mistake is to treat n = 0 as “no ways� because there are no candies, but the problem counts the single empty distribution.

Edge Case: limit = 0

If no child can receive any candy, the only way to distribute n candies is when n = 0 (all children get 0). For any n > 0, the answer is 0. The formula handles this: with limit = 0, the subtraction terms become 3·n(n+1)/2 and 3·(n−1)(n−2)/2, which cancel out to leave 0 for positive n and 1 for n = 0. Watch that the second subtraction term does not accidentally go negative; it must be clamped to zero.

Edge Case: n > 3 * limit

If the total candies exceed the maximum possible (3 × limit), there is no way to distribute them without giving someone more than the limit. The formula naturally returns 0 because the inclusion‑exclusion terms cancel completely. For example, n = 10, limit = 3: unbounded count is 66, subtract 3×28 = 84, add back 3×15 = 45, giving 66 − 84 + 45 = 27? Wait, that’s wrong. Let’s recalc: (10+1)(10+2)/2 = 66; subtract 3·(10−3)(10−3+1)/2 = 3·7·8/2 = 84; add back 3·(10−6−1)(10−6)/2 = 3·3·4/2 = 18; total 66 − 84 + 18 = 0. Correct. The key is to compute each term only when its inner expression is positive.

Common Mistakes

• Forgetting to clamp negative terms: In many languages, the formula will produce negative numbers if you don’t check n - limit - 1 > 0 before computing. Always use max(0, ...) or an if‑statement.
• Integer overflow: n can be up to 10^9, so (n+1)*(n+2) exceeds 32‑bit integers. Use 64‑bit integers (e.g., long in Java, long long in C++).
• Confusing the two problems: LeetCode 2922 is “II� – it allows each child to receive 0 candies, unlike some earlier versions that require at least one. Read the problem statement carefully.
• Using combinations with repetition incorrectly: The unbounded count is C(n+2, 2), not C(n, 3) or similar. Derive it from the stars‑and‑bars method.

Alternative Approaches

Besides the closed‑form formula, you can use dynamic programming with a 2D table (dp[i][j] = ways to distribute i candies to j children) which runs in O(n·limit) but is too slow for large inputs. Another approach is to iterate over the number of candies the first child gets (0 to limit) and compute the range for the second child using prefix sums, giving O(limit) time. The inclusion‑exclusion formula is the most efficient at O(1) time and O(1) space, which is why it’s preferred for the constraints of this problem.

When to Use the Formula

Use the closed‑form expression when n or limit is large (up to 10^9) and you need an instant answer. For small values, brute force or DP is fine for verification. The formula also generalizes to more children: for k children, the inclusion‑exclusion sum has k terms, but for exactly 3 children the expression simplifies nicely.

Frequently Asked Questions

What if n is negative?

The problem constraints guarantee n ≥ 0, so you don’t need to handle negative inputs. If you do, the formula would produce nonsense, but it’s not a valid test case.

Why does the answer become 0 when n > 3*limit?

Because each child can receive at most limit candies, the maximum total is 3*limit. If n exceeds that, no distribution satisfies the constraint, so the count is zero. The formula automatically yields 0 through the inclusion‑exclusion cancellation.

Can I use this formula for other numbers of children?

Yes, but the expression changes. For k children, you’d sum over i = 0 to k with alternating signs and binomial coefficients. For 3 children, the formula above is the simplified version.

What is the time complexity of the best solution?

The closed‑form formula runs in O(1) time and O(1) space. That’s optimal for this problem, which expects a solution that handles n and limit up to 10^9.

Why does the calculator show “Cannot compute� for some inputs?

If you enter a negative number for n or limit, the calculator rejects it because the problem only defines non‑negative integers. The formula itself would not be valid for negatives.

Related

• Multi Site Hosting: What to Check Before Buying
• Malware Protection If You Turn Off S Mode
• VLC Sync Subtitles: How to Fix Audio & Sub Delay

in n | Total candies | - | 5 | 0 | 1000000000
in limit | Max per child | - | 3 | 0 | 1000000000
out ways | Number of distributions | - | (n+1)*(n+2)/2 - 3*max(0, n-limit-1)*(n-limit)/2 + 3*max(0, n-2*limit-2)*(n-2*limit-1)/2 | 0