Distribute Candies Among Children II
MedPrompt
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 <= 1061 <= limit <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through all possible combinations of candies for the first two children and then checking if the remaining candies for the third child satisfy the given constraints.
Algorithm
- Initialize a counter
countto 0. - Iterate
c1from 0 tolimit. - Iterate
c2from 0 tolimit. -
Calculate `c3 = n - c1 - c2`. -
If `c3 >= 0` and `c3 <= limit`, increment `count`. - Return
count.
Walkthrough
We can solve this problem by systematically checking every possible distribution.
We use two nested loops. The outer loop iterates through the number of candies for the first child, c1, from 0 up to limit. The inner loop iterates through the number of candies for the second child, c2, from 0 up to limit.
For each pair (c1, c2), we calculate the number of candies the third child would get: c3 = n - c1 - c2.
We then check if this distribution is valid. A distribution is valid if:
- The total number of candies is
n(which is true by our calculation ofc3). - Each child gets a non-negative number of candies (
c1 >= 0,c2 >= 0,c3 >= 0). - No child gets more than
limitcandies (c1 <= limit,c2 <= limit,c3 <= limit). The loop bounds already ensure0 <= c1 <= limitand0 <= c2 <= limit. So, we only need to check if0 <= c3 <= limit. If the distribution is valid, we increment a counter. After checking all combinations, the counter will hold the total number of valid ways.
class Solution { public long distributeCandies(int n, int limit) { long count = 0; for (int i = 0; i <= limit; i++) { for (int j = 0; j <= limit; j++) { if (i + j > n) { // Optimization: if sum of first two is already > n, // no need to continue inner loop break; } int k = n - i - j; if (k >= 0 && k <= limit) { count++; } } } return count; }}Complexity
Time
O(limit^2). The two nested loops each run up to `limit + 1` times in the worst case. For the given constraints (`limit` up to 10^6), this is too slow and will result in a Time Limit Exceeded error.
Space
O(1). We only use a constant amount of extra space for variables.
Trade-offs
Pros
Very simple to understand and implement.
It's a direct translation of the problem's conditions into code.
Cons
Highly inefficient for large values of
limit.Fails to pass within the time limits for the given constraints.
Solutions
Solution
class Solution {public long distributeCandies(int n, int limit) { if (n > 3 * limit) { return 0; } long ans = comb2(n + 2); if (n > limit) { ans -= 3 * comb2(n - limit + 1); } if (n - 2 >= 2 * limit) { ans += 3 * comb2(n - 2 * limit); } return ans; }private long comb2(int n) { return 1L * n * (n - 1) / 2; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.