LeetCode Problem 2927

Difficulty: 🔴 Hard
Topics: Math, Combinatorics

Solution

LeetCode 2927 - Distribute Candies Among Children III

Problem Understanding

We are given two integers, n and limit.

There are exactly three children, and we want to distribute all n candies among them. If we let the number of candies received by the three children be:

$$x_1,\ x_2,\ x_3$$

then the distribution must satisfy:

$$x_1 + x_2 + x_3 = n$$

with the additional restriction:

$$0 \le x_i \le limit$$

for every child.

The task is to count how many different ordered triples (x1, x2, x3) satisfy these conditions.

The order matters. For example, (1,2,2) and (2,1,2) are considered different distributions because different children receive different amounts.

The constraints are extremely large:

• 1 <= n <= 10^8
• 1 <= limit <= 10^8

These limits immediately tell us that any algorithm that iterates through all possible candy assignments is impossible. Even an O(n) solution would be too expensive when n can reach one hundred million.

Instead, we need a mathematical counting approach that runs in constant time.

Several edge cases are important:

• When n > 3 * limit, it is impossible to distribute all candies because even giving every child limit candies is not enough.
• When limit >= n, the upper bound never becomes active, and the answer becomes the standard stars-and-bars count.
• When n is close to 3 * limit, only a small number of distributions may exist.
• Since the answer can be large, we must use 64-bit arithmetic.

Approaches

Brute Force

A straightforward solution is to try every possible amount for the first child and every possible amount for the second child.

For each pair (x1, x2), we can compute:

$$x_3 = n - x_1 - x_2$$

and check whether:

$$0 \le x_3 \le limit$$

If so, we count the distribution.

This approach is correct because every possible distribution is examined exactly once.

However, the complexity is enormous. Even if we only iterate values up to limit, the running time is roughly:

$$O(limit^2)$$

With limit as large as 10^8, this is completely infeasible.

Key Insight: Inclusion-Exclusion

Without the upper bound, the number of non-negative integer solutions to:

$$x_1+x_2+x_3=n$$

is given by the stars-and-bars formula:

$$\binom{n+2}{2}$$

The difficulty comes from the constraint:

$$x_i \le limit$$

Instead of counting valid solutions directly, we count all solutions and subtract those that violate the limit.

Let:

• A1 = solutions where x1 > limit
• A2 = solutions where x2 > limit
• A3 = solutions where x3 > limit

We want:

$$|Total| - |A_1 \cup A_2 \cup A_3|$$

Using inclusion-exclusion:

$$|Total| -\sum |A_i| +\sum |A_i\cap A_j| -|A_1\cap A_2\cap A_3|$$

Each term can be transformed into another stars-and-bars problem.

If x1 > limit, define:

$$y_1=x_1-(limit+1)$$

Then:

$$y_1+x_2+x_3=n-(limit+1)$$

The number of such solutions is:

$$\binom{n-(limit+1)+2}{2}$$

whenever the upper value is non-negative.

The same reasoning applies to intersections of two or three violating variables.

This yields an O(1) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(limit²)	O(1)	Enumerates all possible assignments
Optimal	O(1)	O(1)	Uses stars-and-bars with inclusion-exclusion

Algorithm Walkthrough

1. Define a helper function that computes the number of non-negative integer solutions to:

$$a+b+c=s$$

Using stars and bars:

$$\binom{s+2}{2}$$

If s < 0, return 0 because no solutions exist. 2. Count all unconstrained solutions:

$$Total=\binom{n+2}{2}$$ 3. Count solutions where one specific child exceeds the limit.

For example, if child 1 receives at least limit+1 candies, substitute:

$$y_1=x_1-(limit+1)$$

Then:

$$y_1+x_2+x_3=n-(limit+1)$$

giving:

$$\binom{n-(limit+1)+2}{2}$$

solutions.

Since any of the three children can be the violating child, multiply by 3. 4. Count solutions where two children exceed the limit simultaneously.

After shifting both variables:

$$y_1+y_2+x_3=n-2(limit+1)$$

which contributes:

$$\binom{n-2(limit+1)+2}{2}$$

There are:

$$\binom{3}{2}=3$$

such pairs. 5. Count solutions where all three children exceed the limit.

After shifting all variables:

$$y_1+y_2+y_3=n-3(limit+1)$$

contributing:

$$\binom{n-3(limit+1)+2}{2}$$ 6. Apply inclusion-exclusion:

$$Answer= T -3S_1 +3S_2 -S_3$$ 7. Return the resulting value.

Why it works

Stars and bars correctly counts all non-negative integer solutions to a sum equation. Every invalid distribution belongs to at least one set where a child exceeds the limit. Inclusion-exclusion guarantees that solutions violating multiple constraints are neither undercounted nor overcounted. Therefore the final formula counts exactly the distributions satisfying all upper-bound requirements.

Python Solution

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        def count(sum_value: int) -> int:
            if sum_value < 0:
                return 0
            return (sum_value + 2) * (sum_value + 1) // 2

        k = limit + 1

        return (
            count(n)
            - 3 * count(n - k)
            + 3 * count(n - 2 * k)
            - count(n - 3 * k)
        )

The helper function count(sum_value) computes the number of non-negative integer solutions to:

$$a+b+c=sum_value$$

using the stars-and-bars formula. If the sum becomes negative, there are no solutions, so the function returns zero.

The variable k stores limit + 1, which is the amount by which a variable must exceed the limit before it becomes invalid.

The main return statement directly implements the inclusion-exclusion formula. The first term counts all solutions, the second subtracts solutions where one child exceeds the limit, the third restores solutions counted twice because two children exceed the limit, and the final term removes solutions where all three children exceed the limit.

Since every term is computed with simple arithmetic, the algorithm runs in constant time.

Go Solution

func distributeCandies(n int, limit int) int64 {
	count := func(sumValue int) int64 {
		if sumValue < 0 {
			return 0
		}
		s := int64(sumValue)
		return (s + 2) * (s + 1) / 2
	}

	k := limit + 1

	return count(n) -
		3*count(n-k) +
		3*count(n-2*k) -
		count(n-3*k)
}

The Go implementation follows exactly the same mathematical formula. The main difference is that all combinatorial calculations are performed using int64 to avoid overflow. With values up to 10^8, intermediate computations can reach approximately 10^16, which exceeds the range of a 32-bit integer.

Worked Examples

Example 1

Input

n = 5
limit = 2

Compute:

k = limit + 1 = 3

Term	Formula	Value
Total	count(5)	21
Single violations	count(2)	6
Double violations	count(-1)	0
Triple violations	count(-4)	0

Applying inclusion-exclusion:

Step	Calculation	Result
Start	21	21
Subtract singles	21 - 3×6	3
Add doubles	3 + 3×0	3
Subtract triples	3 - 0	3

Final answer:

3

Example 2

Input

n = 3
limit = 3

Compute:

k = 4

Term	Formula	Value
Total	count(3)	10
Single violations	count(-1)	0
Double violations	count(-5)	0
Triple violations	count(-9)	0

Applying inclusion-exclusion:

Step	Calculation	Result
Start	10	10
Subtract singles	10 - 0	10
Add doubles	10 + 0	10
Subtract triples	10 - 0	10

Final answer:

10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic operations are performed
Space	O(1)	No auxiliary data structures are used

The algorithm evaluates the stars-and-bars formula four times and combines the results through inclusion-exclusion. The number of operations does not depend on either n or limit, making the solution constant time and constant space.

Test Cases

sol = Solution()

assert sol.distributeCandies(5, 2) == 3      # example 1
assert sol.distributeCandies(3, 3) == 10     # example 2

assert sol.distributeCandies(1, 1) == 3      # one candy, three placements
assert sol.distributeCandies(2, 1) == 3      # only permutations of (1,1,0)
assert sol.distributeCandies(3, 1) == 1      # exactly (1,1,1)

assert sol.distributeCandies(4, 1) == 0      # impossible, exceeds total capacity
assert sol.distributeCandies(10, 3) == 0     # n > 3 * limit

assert sol.distributeCandies(0, 5) == 1      # all children receive 0
assert sol.distributeCandies(2, 10) == 6     # unconstrained stars-and-bars

assert sol.distributeCandies(6, 2) == 1      # only (2,2,2)
assert sol.distributeCandies(5, 3) == 12     # mixed inclusion-exclusion case

assert sol.distributeCandies(100000000, 100000000) == 5000000150000001
# large values, upper bound inactive

Test Summary

Test	Why
(5, 2)	First official example
(3, 3)	Second official example
(1, 1)	Smallest nontrivial distribution
(2, 1)	Limited capacity with multiple permutations
(3, 1)	Exactly one valid assignment
(4, 1)	Impossible due to capacity limit
(10, 3)	Much larger than total capacity
(0, 5)	Degenerate stars-and-bars case
(2, 10)	Upper bound never activates
(6, 2)	Single valid distribution
(5, 3)	General inclusion-exclusion scenario
(100000000, 100000000)	Maximum-scale arithmetic test

Edge Cases

When n > 3 * limit

The three children together can hold at most 3 * limit candies. If n exceeds this value, no valid distribution exists. A naive implementation may forget this condition and accidentally produce a positive count. The inclusion-exclusion formula naturally evaluates to zero because all feasible solution counts cancel out correctly.

When the Upper Bound Never Matters

If limit >= n, no child can possibly exceed the limit because the total number of candies is only n. In this situation the answer should reduce to the unconstrained stars-and-bars formula:

$$\binom{n+2}{2}$$

The implementation handles this automatically because all inclusion-exclusion correction terms receive negative arguments and therefore contribute zero.

When a Variable Shift Produces a Negative Sum

During inclusion-exclusion we evaluate terms such as:

$$count(n-k)$$

or

$$count(n-2k)$$

These values may be negative. A common bug is attempting to apply the combinatorial formula directly, which would produce invalid results. The helper function explicitly returns zero whenever the sum is negative, matching the fact that no non-negative solutions can exist.

When Values Are Near the Maximum Constraints

With n and limit up to 10^8, intermediate combinatorial values can reach roughly:

$$\binom{100000002}{2}$$

which is about 5 × 10^15. A 32-bit integer cannot store such values. The Go solution uses int64, and Python's arbitrary-precision integers handle these values automatically. This guarantees correctness for all valid inputs.