Distribute Candies Among Children II

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 <= 10^6
1 <= limit <= 10^6

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 get more than limit candies.

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): 3 * C(n - (limit+1) + 2, 2).

Add back cases where at least two children get more than limit candies (overlap):

For two children, both get at least limit+1, so a' + b' + c = n - 2*(limit+1).
There are 3 such cases: 3 * C(n - 2 * (limit+1) + 2, 2).

Subtract cases where all three children get more than limit candies:

All get at least limit+1, so a' + b' + c' = n - 3*(limit+1).
Only 1 such case: C(n - 3*(limit+1) + 2, 2).

For each combination, if the value inside C(x, 2) is negative, treat as 0.
Return the final answer.

Code

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

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

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

      ans: int = comb2(n + 2)
      ans -= 3 * comb2(n - (limit + 1) + 2)
      ans += 3 * comb2(n - 2 * (limit + 1) + 2)
      ans -= comb2(n - 3 * (limit + 1) + 2)
      return ans

Complexity

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

Problem#

Examples#

Similar Problems#

Solution#

Method 1 – Inclusion-Exclusion Principle#

Intuition#

Approach#

Code#

Complexity#