Distribute Candies Among Children III

Problem

You are given two positive integers n and limit.

Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

Examples

Example 1:

1
2
3
Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

1
2
3
Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

Solution

Method 1 – Inclusion-Exclusion Principle

Intuition

The problem asks for the number of integer solutions to a + b + c = n with 0 ≤ a, b, c ≤ limit. Without the upper bound, the answer is combinations with repetition: C(n+3-1, 3-1) = C(n+2, 2). The upper bound is handled using the inclusion-exclusion principle: subtract cases where one or more children exceed the limit.

Approach

Count all non-negative integer solutions to a + b + c = n (no upper bound):

Use the formula: C(n+2, 2).

Subtract cases where at least one child gets more than limit candies:

For each child, if they get at least limit+1, set a' = a - (limit+1) ≥ 0, so the equation becomes a' + b + c = n - (limit+1).
There are 3 such cases (one for each child).

Add back cases where two children get more than limit (since subtracted twice):

For each pair, set both a, b ≥ limit+1, so a' + b' + c = n - 2*(limit+1).
There are 3 such cases (for each pair).

Subtract cases where all three get more than limit (added back too many times):

Set all a, b, c ≥ limit+1, so a' + b' + c' = n - 3*(limit+1).
Only 1 such case.

For each case, if the remaining candies is negative, treat as 0 ways.
Sum up using the inclusion-exclusion formula.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
   int distributeCandies(int n, int limit) {
      auto comb = [](int x) -> int {
        if (x < 0) return 0;
        return (x + 2) * (x + 1) / 2;
      };
      int ans = comb(n);
      ans -= 3 * comb(n - (limit + 1));
      ans += 3 * comb(n - 2 * (limit + 1));
      ans -= comb(n - 3 * (limit + 1));
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
   private int comb(int x) {
      if (x < 0) return 0;
      return (x + 2) * (x + 1) / 2;
   }
   public int distributeCandies(int n, int limit) {
      int ans = comb(n);
      ans -= 3 * comb(n - (limit + 1));
      ans += 3 * comb(n - 2 * (limit + 1));
      ans -= comb(n - 3 * (limit + 1));
      return ans;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
   def distributeCandies(self, n: int, limit: int) -> int:
      def comb(x: int) -> int:
        if x < 0:
           return 0
        return (x + 2) * (x + 1) // 2
      ans: int = comb(n)
      ans -= 3 * comb(n - (limit + 1))
      ans += 3 * comb(n - 2 * (limit + 1))
      ans -= comb(n - 3 * (limit + 1))
      return ans

Complexity

⏰ Time complexity: O(1) (constant time, only arithmetic operations)
🧺 Space complexity: O(1) (no extra space)

Problem#

Examples#

Similar Problems#

Solution#

Method 1 – Inclusion-Exclusion Principle#

Intuition#

Approach#

Code#

Complexity#