1. Distribute Candies Among Children I (LeetCode)
Model answer
The task
Count the ways to give all n candies to three children, where each child receives a whole number of candies between zero and limit, inclusive.
Key idea
Choose how many candies the first two children receive; the third child’s amount is then determined. Count the choice if that amount is also within the allowed range.
Approach
- Enumerate the first child’s amount from zero to
min(n, limit). - For each choice, enumerate the second child’s amount over the same range.
- Compute the remaining candies for the third child.
- Increment the count if the remainder is between zero and
limit.
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
ways = 0
# Choose amounts for the first two children.
for first in range(min(n, limit) + 1):
for second in range(min(n, limit) + 1):
third = n - first - second
if 0 <= third <= limit:
ways += 1
return ways
Complexity:
- Time: O(min(n, limit)²), for enumerating pairs of amounts.
- Space: O(1), using only a few variables.
Common follow-ups
- How could you avoid enumeration? Use counting formulas or inclusion-exclusion to count bounded nonnegative solutions.
- What if there are more than three children? Count assignments across
kchildren, using dynamic programming or a generalized counting formula. - What if children have different limits? Enumerate choices while checking each child’s individual bound.