# 2928. Distribute Candies Among Children I

## Description

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 <= 50
• 1 <= limit <= 50

## Solutions

Solution 1: Combinatorial Mathematics + Principle of Inclusion-Exclusion

According to the problem description, we need to distribute $n$ candies to $3$ children, with each child receiving between $[0, limit]$ candies.

This is equivalent to placing $n$ balls into $3$ boxes. Since the boxes can be empty, we can add $3$ virtual balls, and then use the method of inserting partitions, i.e., there are a total of $n + 3$ balls, and we insert $2$ partitions among the $n + 3 - 1$ positions, thus dividing the actual $n$ balls into $3$ groups, and allowing the boxes to be empty. Therefore, the initial number of schemes is $C_{n + 2}^2$.

We need to exclude the schemes where the number of balls in a box exceeds $limit$. Consider that there is a box where the number of balls exceeds $limit$, then the remaining balls (including virtual balls) have at most $n + 3 - (limit + 1) = n - limit + 2$, and the number of positions is $n - limit + 1$, so the number of schemes is $C_{n - limit + 1}^2$. Since there are $3$ boxes, the number of such schemes is $3 \times C_{n - limit + 1}^2$. In this way, we will exclude too many schemes where the number of balls in two boxes exceeds $limit$ at the same time, so we need to add the number of such schemes, i.e., $3 \times C_{n - 2 \times limit}^2$.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

• 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 ans


• func distributeCandies(n int, limit int) int {
comb2 := func(n int) int {
return n * (n - 1) / 2
}
if n > 3*limit {
return 0
}
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
}

• function distributeCandies(n: number, limit: number): number {
const comb2 = (n: number) => (n * (n - 1)) / 2;
if (n > 3 * limit) {
return 0;
}
let 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;
}