Distribute Candies Among Children II

How it works

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.

Steps

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.

Complexity

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

Things to watch for

Forgetting the Lower Bound for Child C

When calculating valid values for child B, you must ensure child C does not exceed the limit. The lower bound b_min = max(0, n - a - limit) ensures that c = n - a - b stays within bounds.

Off-by-One Errors in Loop Bounds

When iterating through candy values, remember that both 0 and limit are valid amounts. Using range(limit) instead of range(limit + 1) misses the case where a child gets exactly limit candies.

Incorrect Inclusion-Exclusion Signs

The inclusion-exclusion principle requires alternating signs: add for 0 violations, subtract for 1 violation, add for 2 violations, subtract for 3 violations. Getting the sign wrong produces incorrect results.

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

class Solution {
public:
    long long distributeCandies(int n, int limit) {
        int C3[4] = {1, 3, 3, 1};
        long long res = 0;
        for (int j = 0; j < 4; j++) {
            long long m = n - j * (limit + 1);
            if (m < 0) continue;
            long long ways = (m + 2) * (m + 1) / 2;
            int sign = (j % 2 == 0 ? 1 : -1);
            res += sign * C3[j] * ways;
        }
        return res;
    }
};