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).

Constraints:

  • 1 <= n <= 50
  • 1 <= limit <= 50

Similar Problems

Distribute Candies Among Children II Distribute Candies Among Children III

Solution

Method 1 – Inclusion-Exclusion Principle

Intuition

The problem asks for the number of ways to distribute n candies among 3 children, with each child getting at most limit candies. If there were no upper limit, the answer would be the number of non-negative integer solutions to a + b + c = n, which is C(n+3-1, 3-1) = C(n+2, 2). The limit constraint can be handled using the inclusion-exclusion principle: subtract cases where one or more children exceed the limit.

Approach

  1. Count all non-negative solutions to a + b + c = n (no limits): use the stars and bars formula.
  2. Subtract cases where at least one child gets more than limit candies:
  • For each subset of children, use inclusion-exclusion to add or subtract the number of ways where those children get at least limit+1 candies.
  1. For each subset (represented by a bitmask of 3 bits), calculate the reduced candies after assigning at least limit+1 to selected children.
  2. Sum up the contributions with the correct sign (add or subtract based on subset size).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
   int distributeCandies(int n, int limit) {
      int ans = 0;
      for (int mask = 0; mask < 8; ++mask) {
        int cnt = 0, rem = n;
        for (int i = 0; i < 3; ++i) {
           if (mask & (1 << i)) {
              rem -= (limit + 1);
              cnt++;
           }
        }
        if (rem < 0) continue;
        int ways = (rem + 2) * (rem + 1) / 2;
        ans += (cnt % 2 == 0 ? ways : -ways);
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
   public int distributeCandies(int n, int limit) {
      int ans = 0;
      for (int mask = 0; mask < 8; ++mask) {
        int cnt = 0, rem = n;
        for (int i = 0; i < 3; ++i) {
           if ((mask & (1 << i)) != 0) {
              rem -= (limit + 1);
              cnt++;
           }
        }
        if (rem < 0) continue;
        int ways = (rem + 2) * (rem + 1) / 2;
        ans += (cnt % 2 == 0 ? ways : -ways);
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
   def distributeCandies(self, n: int, limit: int) -> int:
      ans = 0
      for mask in range(8):
        cnt = 0
        rem = n
        for i in range(3):
           if (mask >> i) & 1:
              rem -= (limit + 1)
              cnt += 1
        if rem < 0:
           continue
        ways = (rem + 2) * (rem + 1) // 2
        ans += ways if cnt % 2 == 0 else -ways
      return ans

Complexity

  • ⏰ Time complexity: O(1) (since 3 children, only 8 subsets)
  • 🧺 Space complexity: O(1)