Welcome to Subscribe On Youtube

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

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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) 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)
    }
    
  • 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;
    }
    
    

All Problems

All Solutions