problemmediumalgorithmsleetcode-2929leetcode 2929leetcode2929

Distribute Candies Among Children II

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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:

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:

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

Similar Problems

[Distribute Candies Among Children I](distribute-candies-among-children-i) [Distribute Candies Among Children III](distribute-candies-among-children-iii)

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

  1. Count all non-negative integer solutions to a + b + c = n (no upper bound):
  • Use the formula: C(n+2, 2).
  1. 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).
  1. 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).
  1. 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).
  1. For each combination, if the value inside C(x, 2) is negative, treat as 0.
  2. Return the final answer.

Code

C++
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;
  }
};
Java
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;
   }   
}
Python
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)

Comments