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 <= 106class Solution {
public long distributeCandies(int n, int limit) {
long ans = 0;
limit = Math.min(limit, n);
for (int i = 0; i <= limit; i++) {
if (n - i > 2 * limit) // invalid cases
continue;
// j_Range => [0, Math.min(n - i, limit)];
// but again ... k = n - i - j <= limit or n - i - limit <= j
// so j_range => [Math.max(0, n-i-limit),Math.min(n-i, limit)]
ans += Math.min(n - i, limit) - Math.max(0, n - i - limit) + 1;
}
return Math.max(ans, 0);
}
}class Solution {
public long distributeCandies(int n, int limit) {
// return combination(n + 2, 2) - 3 * combination(n + 2 - (limit + 1), 2)
// + 3 * combination(n + 2 - 2 * (limit + 1), 2)
// - combination(n + 2 - 3 * (limit + 1), 2);
return combination(n + 2) - 3 * combination(n - limit + 1) + 3 * combination(n - 2 * limit)
- combination(n - 3 * limit - 1);
}
private long combination(int n) { // nCr, where r=2 => nC2
if (n < 2) // cant choose 2 items from a collection containing less that n objects
return 0;
return (long) n * (n - 1) / 2;
}
}class Solution {
public long distributeCandies(int n, int limit) {
// return combination(n + 2, 2) - 3 * combination(n + 2 - (limit + 1), 2)
// + 3 * combination(n + 2 - 2 * (limit + 1), 2)
// - combination(n + 2 - 3 * (limit + 1), 2);
return combination(n + 2) - 3 * combination(n - limit + 1) + 3 * combination(n - 2 * limit)
- combination(n - 3 * limit - 1);
}
private long combination(int n) { // nCr, where r=2 => nC2
if (n < 2) // cant choose 2 items from a collection containing less that n objects
return 0;
return (long) n * (n - 1) / 2;
}
}