Distribute Candies Among Children II
Distribute Candies Among Children II is a medium arrays & hashing problem solved with the math / number theory pattern.
The best approach, optimal (inclusion-exclusion, o(1)), runs in O(1) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try the first two shares) up.
Problem
You have n candies to hand out to exactly 3 children. Every candy must be given away, a child may receive zero candies, and no child may receive more than limit candies.
Return the number of different ways to do it. Two ways are different if at least one child receives a different number of candies.
Examples
Example 1
- Input
n = 4, limit = 2- Output
6- Why
- The splits are (0,2,2), (2,0,2), (2,2,0), (1,1,2), (1,2,1) and (2,1,1); anything with a 3 or 4 breaks the limit.
Example 2
- Input
n = 2, limit = 5- Output
6- Why
- The limit never matters here: (2,0,0) in 3 orders plus (1,1,0) in 3 orders.
Example 3
- Input
n = 7, limit = 2- Output
0- Why
- Three children can hold at most 6 candies in total.
Constraints
1 <= n <= 10^61 <= limit <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try the first two shares) | O(min(n, limit)²) | O(1) |
| Better (fix the first child, count the rest) | O(min(n, limit)) | O(1) |
| Optimal (inclusion-exclusion, O(1)) | O(1) | O(1) |
1Brute force (try the first two shares)
O(min(n, limit)²)Two nested loops over at most min(n, limit) + 1 values each.O(1)Only a counter.Loop over the first child's amount a and the second child's amount b, each from 0 to min(n, limit). The third child gets n - a - b; count the pair if that value is between 0 and limit.
- For a from 0 to min(n, limit), for b from 0 to min(n - a, limit):
- If n - a - b <= limit, count it.
- Return the count.
class Solution {
public long distributeCandies(int n, int limit) {
long count = 0;
for (int a = 0; a <= Math.min(n, limit); a++)
for (int b = 0; b <= Math.min(n - a, limit); b++)
if (n - a - b <= limit) count++;
return count;
}
}class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
count = 0
for a in range(min(n, limit) + 1):
for b in range(min(n - a, limit) + 1):
if n - a - b <= limit:
count += 1
return countclass Solution {
public:
long long distributeCandies(int n, int limit) {
long long count = 0;
for (int a = 0; a <= min(n, limit); a++)
for (int b = 0; b <= min(n - a, limit); b++)
if (n - a - b <= limit) count++;
return count;
}
};function distributeCandies(n, limit) {
let count = 0;
for (let a = 0; a <= Math.min(n, limit); a++)
for (let b = 0; b <= Math.min(n - a, limit); b++)
if (n - a - b <= limit) count++;
return count;
}2Better (fix the first child, count the rest)
O(min(n, limit))One loop over the first child's possible shares, constant work each.O(1)A few counters.Once the first child's share a is fixed, r = n - a candies remain for two children. The second child can take any b with max(0, r - limit) <= b <= min(r, limit), and the third child's share is then determined. Add the length of that interval when it is non-empty.
- For a from 0 to min(n, limit): r = n - a.
- lo = max(0, r - limit), hi = min(r, limit).
- If lo <= hi, add hi - lo + 1.
class Solution {
public long distributeCandies(int n, int limit) {
long count = 0;
for (int a = 0; a <= Math.min(n, limit); a++) {
int r = n - a;
int lo = Math.max(0, r - limit), hi = Math.min(r, limit);
if (lo <= hi) count += hi - lo + 1;
}
return count;
}
}class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
count = 0
for a in range(min(n, limit) + 1):
r = n - a
lo, hi = max(0, r - limit), min(r, limit)
if lo <= hi:
count += hi - lo + 1
return countclass Solution {
public:
long long distributeCandies(int n, int limit) {
long long count = 0;
for (int a = 0; a <= min(n, limit); a++) {
int r = n - a;
int lo = max(0, r - limit), hi = min(r, limit);
if (lo <= hi) count += hi - lo + 1;
}
return count;
}
};function distributeCandies(n, limit) {
let count = 0;
for (let a = 0; a <= Math.min(n, limit); a++) {
const r = n - a;
const lo = Math.max(0, r - limit), hi = Math.min(r, limit);
if (lo <= hi) count += hi - lo + 1;
}
return count;
}3Optimal (inclusion-exclusion, O(1))
O(1)Four evaluations of a closed formula.O(1)No extra storage.Without a limit, m candies can be split among 3 children in ways(m) = (m + 2)(m + 1) / 2 ways (stars and bars), and ways(m) = 0 for negative m. If a particular child gets more than limit, hand it limit + 1 up front and split the rest freely. Inclusion-exclusion over the set of children that break the limit gives ways(n) - 3·ways(n - (limit + 1)) + 3·ways(n - 2(limit + 1)) - ways(n - 3(limit + 1)).
- Define ways(m) = 0 if m < 0, else (m + 2)(m + 1) / 2, using 64-bit arithmetic.
- Let s = limit + 1.
- Return ways(n) - 3 * ways(n - s) + 3 * ways(n - 2s) - ways(n - 3s).
class Solution {
public long distributeCandies(int n, int limit) {
long s = limit + 1L;
return ways(n) - 3 * ways(n - s) + 3 * ways(n - 2 * s) - ways(n - 3 * s);
}
private long ways(long m) {
if (m < 0) return 0;
return (m + 2) * (m + 1) / 2;
}
}class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
def ways(m: int) -> int:
return 0 if m < 0 else (m + 2) * (m + 1) // 2
s = limit + 1
return ways(n) - 3 * ways(n - s) + 3 * ways(n - 2 * s) - ways(n - 3 * s)class Solution {
public:
long long distributeCandies(int n, int limit) {
long long s = limit + 1LL;
return ways(n) - 3 * ways(n - s) + 3 * ways(n - 2 * s) - ways(n - 3 * s);
}
private:
long long ways(long long m) {
if (m < 0) return 0;
return (m + 2) * (m + 1) / 2;
}
};function distributeCandies(n, limit) {
const ways = (m) => (m < 0 ? 0 : ((m + 2) * (m + 1)) / 2);
const s = limit + 1;
return ways(n) - 3 * ways(n - s) + 3 * ways(n - 2 * s) - ways(n - 3 * s);
}Edge cases to test
n > 3 * limit: the answer is 0limit >= n: the limit never binds, so the answer is (n + 2)(n + 1) / 2n = 3 * limit: exactly one way, everyone gets limit- Large inputs where the count exceeds the 32-bit range (around 5 * 10^11)
Hints
Hint 1
Fix how many candies the first child gets. How many valid choices remain for the second child, given that the third child's share is then forced?
Hint 2
For the first child getting a, the second child's amount b must satisfy 0 <= b <= limit and 0 <= n - a - b <= limit. That is an interval, so you can count it in O(1).
Hint 3
For an O(1) answer, count all ways without the limit, (m + 2)(m + 1) / 2 for m candies, and use inclusion-exclusion over which children receive more than limit.
FAQ
What is the best time complexity for Distribute Candies Among Children II?
Optimal (inclusion-exclusion, O(1)) runs in O(1) time and O(1) extra space. Four evaluations of a closed formula.
Which pattern does Distribute Candies Among Children II use?
It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Water and Jug Problem.
Is there a brute force solution for Distribute Candies Among Children II?
Yes. Brute force (try the first two shares) takes O(min(n, limit)²) time and O(1) space. Loop over the first child's amount a and the second child's amount b, each from 0 to min(n, limit).
Which edge cases should I test for Distribute Candies Among Children II?
n 3 limit: the answer is 0; limit = n: the limit never binds, so the answer is (n + 2)(n + 1) / 2; n = 3 limit: exactly one way, everyone gets limit; Large inputs where the count exceeds the 32-bit range (around 5 10^11).