2929. Distribute Candies Among Children II
Description
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.
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 <= 106
1 <= limit <= 106
Solutions
Solution 1: Combinatorial Mathematics + Principle of Inclusion-Exclusion
According to the problem description, we need to distribute $n$ candies to $3$ children, with each child receiving between $[0, limit]$ candies.
This is equivalent to placing $n$ balls into $3$ boxes. Since the boxes can be empty, we can add $3$ virtual balls, and then use the method of inserting partitions, i.e., there are a total of $n + 3$ balls, and we insert $2$ partitions among the $n + 3 - 1$ positions, thus dividing the actual $n$ balls into $3$ groups, and allowing the boxes to be empty. Therefore, the initial number of schemes is $C_{n + 2}^2$.
We need to exclude the schemes where the number of balls in a box exceeds $limit$. Consider that there is a box where the number of balls exceeds $limit$, then the remaining balls (including virtual balls) have at most $n + 3 - (limit + 1) = n - limit + 2$, and the number of positions is $n - limit + 1$, so the number of schemes is $C_{n - limit + 1}^2$. Since there are $3$ boxes, the number of such schemes is $3 \times C_{n - limit + 1}^2$. In this way, we will exclude too many schemes where the number of balls in two boxes exceeds $limit$ at the same time, so we need to add the number of such schemes, i.e., $3 \times C_{n - 2 \times limit}^2$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|