Skip to content

2929. Distribute Candies Among Children II

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

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

 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