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:
|
|
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
- Count all non-negative solutions to
a + b + c = n
(no limits): use the stars and bars formula. - 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.
- For each subset (represented by a bitmask of 3 bits), calculate the reduced candies after assigning at least
limit+1
to selected children. - Sum up the contributions with the correct sign (add or subtract based on subset size).
Code
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(1)
(since 3 children, only 8 subsets) - 🧺 Space complexity:
O(1)