Distribute Candies Among Children II

• Initialize a counter count to 0.
• Iterate c1 from 0 to limit.
• Iterate c2 from 0 to limit.
• Calculate `c3 = n - c1 - c2`.
• If `c3 >= 0` and `c3 <= limit`, increment `count`.
• Return count.

We can solve this problem by systematically checking every possible distribution. We use two nested loops. The outer loop iterates through the number of candies for the first child, c1, from 0 up to limit. The inner loop iterates through the number of candies for the second child, c2, from 0 up to limit. For each pair (c1, c2), we calculate the number of candies the third child would get: c3 = n - c1 - c2. We then check if this distribution is valid. A distribution is valid if:

1. The total number of candies is n (which is true by our calculation of c3).
2. Each child gets a non-negative number of candies (c1 >= 0, c2 >= 0, c3 >= 0).
3. No child gets more than limit candies (c1 <= limit, c2 <= limit, c3 <= limit). The loop bounds already ensure 0 <= c1 <= limit and 0 <= c2 <= limit. So, we only need to check if 0 <= c3 <= limit. If the distribution is valid, we increment a counter. After checking all combinations, the counter will hold the total number of valid ways.

1class Solution {2    public long distributeCandies(int n, int limit) {3        long count = 0;4        for (int i = 0; i <= limit; i++) {5            for (int j = 0; j <= limit; j++) {6                if (i + j > n) {7                    // Optimization: if sum of first two is already > n,8                    // no need to continue inner loop9                    break; 10                }11                int k = n - i - j;12                if (k >= 0 && k <= limit) {13                    count++;14                }15            }16        }17        return count;18    }19}

• Initialize a counter count to 0.
• Iterate c1 from 0 to min(n, limit).
• Calculate the remaining candies: rem_n = n - c1.
• Determine the lower bound for c2: lower_bound = max(0, rem_n - limit).
• Determine the upper bound for c2: upper_bound = min(limit, rem_n).
• If upper_bound >= lower_bound, add (upper_bound - lower_bound + 1) to count.
• Return count.

Instead of iterating through possibilities for both the first and second child, we can fix the number of candies for one child, say c1, and then determine the number of ways to distribute the remaining candies between the other two. Let the first child receive c1 candies, where 0 <= c1 <= min(n, limit). The remaining n - c1 candies must be distributed between the second and third child: c2 + c3 = n - c1. We also have the constraints 0 <= c2 <= limit and 0 <= c3 <= limit. Let rem_n = n - c1. We need to find the number of solutions to c2 + c3 = rem_n with 0 <= c2, c3 <= limit. From c3 = rem_n - c2, the constraint 0 <= c3 <= limit becomes 0 <= rem_n - c2 <= limit. This gives two inequalities for c2:

1. rem_n - c2 >= 0 => c2 <= rem_n
2. rem_n - c2 <= limit => c2 >= rem_n - limit Combining all constraints on c2 (0 <= c2 <= limit, c2 <= rem_n, c2 >= rem_n - limit), we get the valid range for c2: max(0, rem_n - limit) <= c2 <= min(limit, rem_n). The number of integer solutions for c2 in this range is min(limit, rem_n) - max(0, rem_n - limit) + 1. We iterate c1 from 0 to min(n, limit), calculate this quantity for each c1, and sum them up to get the total count.

1class Solution {2    public long distributeCandies(int n, int limit) {3        long count = 0;4        for (int i = 0; i <= Math.min(n, limit); i++) {5            int remaining_n = n - i;6            // We need to find solutions for c2 + c3 = remaining_n7            // where 0 <= c2, c3 <= limit8            9            // From c3 = remaining_n - c2, we have 0 <= remaining_n - c2 <= limit10            // This gives: remaining_n - limit <= c2 <= remaining_n11            12            // Combining with 0 <= c2 <= limit, we get:13            // max(0, remaining_n - limit) <= c2 <= min(limit, remaining_n)14            15            int min_c2 = Math.max(0, remaining_n - limit);16            int max_c2 = Math.min(limit, remaining_n);17            18            if (max_c2 >= min_c2) {19                count += (max_c2 - min_c2 + 1);20            }21        }22        return count;23    }24}

• Define a helper function ways(k):
  • If k < 0, return 0.
  • Otherwise, return (long)(k + 2) * (k + 1) / 2.
• Calculate total_ways = ways(n).
• Calculate ways_one_exceeds = ways(n - limit - 1).
• Calculate ways_two_exceeds = ways(n - 2 * (limit + 1)).
• Calculate ways_three_exceeds = ways(n - 3 * (limit + 1)).
• Apply the Inclusion-Exclusion formula: result = total_ways - 3 * ways_one_exceeds + 3 * ways_two_exceeds - ways_three_exceeds.
• Return result.

The problem is equivalent to finding the number of non-negative integer solutions to x1 + x2 + x3 = n subject to x1, x2, x3 <= limit. Step 1: Ignore the upper limit. The number of non-negative solutions to x1 + x2 + x3 = n can be found using stars and bars. The formula is C(n + k - 1, k - 1) where k=3. This gives C(n + 2, 2) = (n + 2) * (n + 1) / 2. Let's create a helper function ways(k) for this calculation, which returns 0 if k < 0. Step 2: Apply Inclusion-Exclusion. We need to subtract the cases where the limit constraint is violated.

• Let P1 be the property that x1 > limit, P2 that x2 > limit, and P3 that x3 > limit. We want to find the total ways minus the ways that have at least one of these properties.
• Subtract cases where one child exceeds the limit: The number of ways where x1 > limit (i.e., x1 >= limit + 1) is found by pre-allocating limit + 1 candies to child 1 and distributing the rest: x1' + x2 + x3 = n - (limit + 1). The number of solutions is ways(n - limit - 1). By symmetry, this is the same for x2 and x3. So we subtract 3 * ways(n - limit - 1).
• Add back cases where two children exceed the limit: We subtracted cases where two children exceed the limit twice. We need to add them back once. The number of ways where x1 > limit and x2 > limit is ways(n - 2 * (limit + 1)). By symmetry, there are 3 such pairs. So we add back 3 * ways(n - 2 * (limit + 1)).
• Subtract cases where three children exceed the limit: These were subtracted three times and added back three times, so they haven't been accounted for correctly. We need to subtract them once. The number of ways is ways(n - 3 * (limit + 1)). Final Formula: The total number of valid ways is ways(n) - 3 * ways(n - limit - 1) + 3 * ways(n - 2 * (limit + 1)) - ways(n - 3 * (limit + 1)).

1class Solution {2    public long distributeCandies(int n, int limit) {3        // Total ways to distribute n candies to 3 children without limit4        long totalWays = ways(n);5        6        // Using Inclusion-Exclusion Principle7        // Let A, B, C be the sets of distributions where child 1, 2, 38        // get more than 'limit' candies respectively.9        // We want to find |U| - |A U B U C|10        // |A U B U C| = |A|+|B|+|C| - (|A n B|+|A n C|+|B n C|) + |A n B n C|11        12        // Case 1: At least one child gets more than 'limit' candies.13        long oneExceeds = 3 * ways(n - limit - 1);14        15        // Case 2: At least two children get more than 'limit' candies.16        long twoExceeds = 3 * ways(n - 2 * (limit + 1));17        18        // Case 3: All three children get more than 'limit' candies.19        long threeExceeds = ways(n - 3 * (limit + 1));20        21        return totalWays - oneExceeds + twoExceeds - threeExceeds;22    }23 24    private long ways(int k) {25        if (k < 0) {26            return 0;27        }28        // C(k+2, 2) = (k+2)*(k+1)/229        // Using long to prevent overflow before division30        return (long)(k + 2) * (k + 1) / 2;31    }32}