problemhardalgorithmsleetcode-2927leetcode 2927leetcode2927

Distribute Candies Among Children III

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

Similar Problems

[Distribute Candies Among Children I](distribute-candies-among-children-i) [Distribute Candies Among Children II](distribute-candies-among-children-ii)

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

  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).
  1. 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).
  1. 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.
  1. For each case, if the remaining candies is negative, treat as 0 ways.
  2. Sum up using the inclusion-exclusion formula.

Code

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

Comments