2929. Distribute Candies Among Children II

2929. Distribute Candies Among Children II

Difficulty: Medium

Topics: Math, Combinatorics, Enumeration

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

Hint:

1. We can enumerate the number of candies of one particular child, let it be i which means 0 <= i <= min(limit, n).
2. Suppose the 2nd child gets j candies. Then 0 <= j <= limit and i + j <= n.
3. The 3rd child will hence get n - i - j candies and we should have 0 <= n - i - j <= limit.
4. After some transformations, for each i, we have max(0, n - i - limit) <= j <= min(limit, n - i), each j corresponding to a solution. So the number of solutions for some i is max(min(limit, n - i) - max(0, n - i - limit) + 1, 0). Sum the expression for every i in [0, min(n, limit)].

Solution:

We need to determine the number of ways to distribute n candies among 3 children such that no child receives more than limit candies. The solution involves using combinatorial mathematics and the inclusion-exclusion principle to efficiently compute the result without iterating through all possible distributions.

Approach

1. Problem Analysis: The problem requires counting the number of non-negative integer solutions to the equation x₁ + x₂ + x₃ = n where 0 ≤ x_i ≤ limit for each i.

2. Combinatorial Insight: The total number of non-negative solutions to the equation without any constraints is given by the stars and bars formula, which is (n + 2)/2. However, we need to subtract the solutions that violate the constraint x_i ≤ limit.

3. Inclusion-Exclusion Principle: To account for the constraints, we use the inclusion-exclusion principle:

   • Total Solutions: Calculate all possible solutions without constraints.
   • Subtract Invalid Solutions: Subtract solutions where at least one child exceeds the limit. This involves considering cases where one child has at least limit + 1 candies.
   • Add Back Over-Subtracted Solutions: Add back solutions where two children exceed the limit (since these were subtracted twice).
   • Subtract Over-Added Solutions: Subtract solutions where all three children exceed the limit (since these were added back in the previous step).

4. Efficiency: The inclusion-exclusion approach allows us to compute the result in constant time O(1) using combinatorial formulas, making it efficient even for large values of n and limit.

Let's implement this solution in PHP: 2929. Distribute Candies Among Children II

<?php
/**
 * @param Integer $n
 * @param Integer $limit
 * @return Integer
 */
function distributeCandies($n, $limit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo distributeCandies(5, 2) . "\n"; // Output: 3
echo distributeCandies(3, 3) . "\n"; // Output: 10
?>

Explanation:

1. Helper Function _f(x)_: This function calculates the number of non-negative integer solutions to x₁ + x₂ + x₃ = x using the stars and bars formula (x + 2)/2. If x is negative, it returns 0 since no solutions exist.

2. Total Solutions: The term f(n) computes all possible distributions of n candies without any constraints.

3. Subtracting Invalid Solutions: The term -3 x f(n - limit - 1) accounts for the cases where at least one child receives more than limit candies. Here, n - limit - 1 adjusts the remaining candies after one child takes limit + 1 candies.

4. Adding Back Over-Subtracted Solutions: The term +3 x f(n - 2 x limit - 2) corrects for the over-subtraction of cases where two children each exceed the limit by limit + 1 candies.

5. Subtracting Over-Added Solutions: The term -f(n - 3 x limit - 3) adjusts for cases where all three children exceed the limit, ensuring these solutions are not counted.

6. Result Calculation: The final result combines these terms to give the number of valid distributions, casting to an integer to ensure the result is correctly formatted.

This approach efficiently computes the solution using combinatorial mathematics, avoiding the need for brute-force iteration and handling large values within optimal time complexity.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub