Distribute Candies Among Children I
EasyPrompt
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 <= 501 <= limit <= 50
Approaches
3 approaches with complexity analysis and trade-offs.
This is a purely mathematical approach that provides a constant-time solution. It uses the 'stars and bars' method to find the total number of ways to distribute n items into 3 bins without an upper limit, and then applies the Principle of Inclusion-Exclusion to subtract the cases where one or more children receive more than limit candies.
Algorithm
- Define a helper function
combinations2(m)that computesC(m, 2). - Calculate the total ways without an upper limit:
ways1 = combinations2(n + 2). - Calculate the ways where at least one child violates the limit:
ways2 = 3 * combinations2(n - limit + 1). - Calculate the ways where at least two children violate the limit:
ways3 = 3 * combinations2(n - 2 * limit). - Calculate the ways where all three children violate the limit:
ways4 = combinations2(n - 3 * limit - 1). - Apply the Principle of Inclusion-Exclusion:
result = ways1 - ways2 + ways3 - ways4. - Return the final
result.
Walkthrough
The problem is equivalent to finding the number of non-negative integer solutions to c1 + c2 + c3 = n subject to 0 <= c_i <= limit.
First, we ignore the upper bound (limit). The number of non-negative solutions to c1 + c2 + c3 = n is given by the stars and bars formula: C(n + 3 - 1, 3 - 1) = C(n + 2, 2).
Next, we use the Principle of Inclusion-Exclusion to handle the c_i <= limit constraint. We subtract the cases where at least one child gets more than limit candies, add back the cases where at least two children get more than limit, and so on.
The final formula is: Ways = C(n+2, 2) - 3 * C(n-limit+1, 2) + 3 * C(n-2*limit, 2) - C(n-3*limit-1, 2).
Here, C(m, 2) is the number of combinations 'm choose 2', which is m * (m - 1) / 2 for m >= 2 and 0 otherwise. This method directly calculates the result without any iteration.
class Solution { public int distributeCandies(int n, int limit) { // Total ways to distribute n candies to 3 children without limit long totalWays = combinations2(n + 2); // Subtract cases where one child gets more than 'limit' candies // n' = n - (limit + 1) long oneChildExceeds = 3 * combinations2(n - limit - 1 + 2); // Add back cases where two children get more than 'limit' candies // n'' = n - 2 * (limit + 1) long twoChildrenExceed = 3 * combinations2(n - 2 * (limit + 1) + 2); // Subtract cases where three children get more than 'limit' candies // n''' = n - 3 * (limit + 1) long threeChildrenExceed = combinations2(n - 3 * (limit + 1) + 2); return (int) (totalWays - oneChildExceeds + twoChildrenExceed - threeChildrenExceed); } private long combinations2(int m) { if (m < 2) { return 0; } return (long) m * (m - 1) / 2; }}Complexity
Time
O(1). The solution involves a fixed number of arithmetic calculations, regardless of the input values `n` and `limit`.
Space
O(1). Only a few variables are needed to store the intermediate and final results.
Trade-offs
Pros
The most efficient solution with constant time complexity.
Elegant mathematical solution.
Cons
Requires knowledge of combinatorics and the Principle of Inclusion-Exclusion.
Less intuitive and harder to derive than iterative solutions.
Solutions
Solution
class Solution {public int 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 (int)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.