Distribute Candies Among Children I

EASY

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

Approaches

Checkout 3 different approaches to solve Distribute Candies Among Children I. Click on different approaches to view the approach and algorithm in detail.

Combinatorics with Inclusion-Exclusion Principle

This is a purely mathematical approach that provides a constant-time solution. It uses the 'stars and bars' method to find the total number of ways to distribute n items into 3 bins without an upper limit, and then applies the Principle of Inclusion-Exclusion to subtract the cases where one or more children receive more than limit candies.

Algorithm

Define a helper function combinations2(m) that computes C(m, 2).
Calculate the total ways without an upper limit: ways1 = combinations2(n + 2).
Calculate the ways where at least one child violates the limit: ways2 = 3 * combinations2(n - limit + 1).
Calculate the ways where at least two children violate the limit: ways3 = 3 * combinations2(n - 2 * limit).
Calculate the ways where all three children violate the limit: ways4 = combinations2(n - 3 * limit - 1).
Apply the Principle of Inclusion-Exclusion: result = ways1 - ways2 + ways3 - ways4.
Return the final result.

The problem is equivalent to finding the number of non-negative integer solutions to c1 + c2 + c3 = n subject to 0 <= c_i <= limit.

First, we ignore the upper bound (limit). The number of non-negative solutions to c1 + c2 + c3 = n is given by the stars and bars formula: C(n + 3 - 1, 3 - 1) = C(n + 2, 2).

Next, we use the Principle of Inclusion-Exclusion to handle the c_i <= limit constraint. We subtract the cases where at least one child gets more than limit candies, add back the cases where at least two children get more than limit, and so on.

The final formula is: Ways = C(n+2, 2) - 3 * C(n-limit+1, 2) + 3 * C(n-2*limit, 2) - C(n-3*limit-1, 2).

Here, C(m, 2) is the number of combinations 'm choose 2', which is m * (m - 1) / 2 for m >= 2 and 0 otherwise. This method directly calculates the result without any iteration.

class Solution {
    public int distributeCandies(int n, int limit) {
        // Total ways to distribute n candies to 3 children without limit
        long totalWays = combinations2(n + 2);

        // Subtract cases where one child gets more than 'limit' candies
        // n' = n - (limit + 1)
        long oneChildExceeds = 3 * combinations2(n - limit - 1 + 2);

        // Add back cases where two children get more than 'limit' candies
        // n'' = n - 2 * (limit + 1)
        long twoChildrenExceed = 3 * combinations2(n - 2 * (limit + 1) + 2);

        // Subtract cases where three children get more than 'limit' candies
        // n''' = n - 3 * (limit + 1)
        long threeChildrenExceed = combinations2(n - 3 * (limit + 1) + 2);

        return (int) (totalWays - oneChildExceeds + twoChildrenExceed - threeChildrenExceed);
    }

    private long combinations2(int m) {
        if (m < 2) {
            return 0;
        }
        return (long) m * (m - 1) / 2;
    }
}

Complexity Analysis

Time Complexity: O(1). The solution involves a fixed number of arithmetic calculations, regardless of the input values `n` and `limit`.Space Complexity: O(1). Only a few variables are needed to store the intermediate and final results.

Pros and Cons

Pros:

The most efficient solution with constant time complexity.
Elegant mathematical solution.

Cons:

Requires knowledge of combinatorics and the Principle of Inclusion-Exclusion.
Less intuitive and harder to derive than iterative solutions.

Code Solutions

Checking out 3 solutions in different languages for Distribute Candies Among Children I. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Distribute Candies Among Children I

Patterns:

MathCombinatoricsEnumeration

Companies:

Rubrik |