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.
This approach iterates through all possible combinations of candies for the three children using three nested loops. For each combination, it checks if the total number of candies equals n and if each child's candy count is within the limit.
Algorithm
- Initialize a counter
countto 0. - Use a for-loop to iterate through the number of candies for the first child,
i, from 0 tolimit. - Inside the first loop, use a nested for-loop for the second child,
j, from 0 tolimit. - Inside the second loop, use another nested for-loop for the third child,
k, from 0 tolimit. - In the innermost loop, check if the sum
i + j + kequalsn. - If the sum is equal to
n, increment thecount. - After the loops finish, return
count.
Walkthrough
We can simulate the distribution process directly. Let the number of candies for the three children be c1, c2, and c3.
We can use three nested loops, each iterating from 0 to limit, representing the number of candies for each child. Inside the innermost loop, we check if the sum of candies is exactly n: c1 + c2 + c3 == n. The condition that each child gets at most limit candies is inherently handled by the loop bounds.
If the sum condition is met, we increment a counter. After checking all (limit + 1)^3 combinations, the counter will hold the total number of valid distributions.
class Solution { public int distributeCandies(int n, int limit) { int count = 0; for (int i = 0; i <= limit; i++) { for (int j = 0; j <= limit; j++) { for (int k = 0; k <= limit; k++) { if (i + j + k == n) { count++; } } } } return count; }}Complexity
Time
O(limit^3). The three nested loops each run up to `limit + 1` times. For the given constraints (`limit <= 50`), this is feasible (approx. 51*51*51 operations).
Space
O(1). We only use a few variables to store the count and loop indices, so the space used is constant.
Trade-offs
Pros
Very simple to understand and implement.
Guaranteed to be correct if implemented properly.
Cons
Inefficient for larger values of
limit.Performs many redundant calculations.
This approach improves upon the brute-force method by using only two nested loops. After choosing the number of candies for the first two children, the number for the third child is determined automatically. We then just need to check if this number is valid.
Algorithm
- Initialize a counter
countto 0. - Use a for-loop to iterate through the number of candies for the first child,
i, from 0 tolimit. - Inside the first loop, use a nested for-loop for the second child,
j, from 0 tolimit. - Calculate the number of candies for the third child:
k = n - i - j. - Check if
kis valid, i.e.,0 <= k <= limit. - If
kis valid, increment thecount. - After the loops finish, return
count.
Walkthrough
Instead of iterating through possibilities for all three children, we can iterate for the first two and calculate the required candies for the third. Let c1 and c2 be the candies for the first two children. The number of candies for the third child, c3, must be n - c1 - c2 to satisfy the sum condition.
We use two nested loops to iterate c1 from 0 to limit and c2 from 0 to limit. For each pair (c1, c2), we calculate c3 = n - c1 - c2. Then, we check if c3 is a valid number of candies, which means it must satisfy 0 <= c3 <= limit. If c3 is valid, we increment our count of valid distributions.
This eliminates one level of looping, significantly improving performance from O(limit^3) to O(limit^2).
class Solution { public int distributeCandies(int n, int limit) { int count = 0; for (int i = 0; i <= limit; i++) { for (int j = 0; j <= limit; j++) { int k = n - i - j; if (k >= 0 && k <= limit) { count++; } } } return count; }}Complexity
Time
O(limit^2). We have two nested loops, each running up to `limit + 1` times. This is a significant improvement over the O(limit^3) approach.
Space
O(1). Constant extra space is used for the counter and loop variables.
Trade-offs
Pros
More efficient than the three-loop brute-force.
Still relatively easy to understand and implement.
Cons
Not the most optimal solution.
Can be further optimized for even better performance.
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; }}class Solution {public: int distributeCandies(int n, int limit) { auto comb2 = [](int n) { return 1LL * n * (n - 1) / 2; }; if (n > 3 * limit) { return 0; } long 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; }};class Solution: def distributeCandies(self, n: int, limit: int) -> int: if n > 3 * limit: return 0 ans = comb(n + 2, 2) if n > limit: ans -= 3 * comb(n - limit + 1, 2) if n - 2 >= 2 * limit: ans += 3 * comb(n - 2 * limit, 2) return ansVideo 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.