Skip to content

2927. Distribute Candies Among Children III πŸ”’

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

Solutions

Solution 1: Combinatorial Mathematics + Principle of Inclusion-Exclusion

Thinking

We need nonnegative \(x+y+z=n\) with each variable at most \(limit\). \(n\) can be huge, so triple loops are impossible. Stars and bars give \(C_{n+2}^{2}\) without the cap; inclusion-exclusion subtracts the cases with one variable at least \(limit+1\) and adds back two simultaneous violations.

If \(n>3\cdot limit\) the count is \(0\). The binomial arguments are guarded so they stay nonnegative. The formula is \(O(1)\).

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long 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 ans;
    }

    private long comb2(int n) {
        return 1L * n * (n - 1) / 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long 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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func distributeCandies(n int, limit int) int64 {
    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 int64(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

Comments