Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

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

All Problems

All Solutions