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:
|
|
Example 2:
|
|
Similar Problems
Distribute Candies Among Children I 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
- 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
, seta' = a - (limit+1) ≥ 0
, so the equation becomesa' + 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
, soa' + 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
, soa' + 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
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(1)
(constant time, only arithmetic operations) - 🧺 Space complexity:
O(1)
(no extra space)