LeetCode 2929 - Distribute Candies Among Children II

The problem asks us to calculate the total number of ways to distribute n candies among exactly three children, with the constraint that no child can receive more than limit candies.

leetcodemediummathcombinatoricsenumeration

LeetCode Problem 2929

Difficulty: 🟡 Medium
Topics: Math, Combinatorics, Enumeration

Solution

Problem Understanding

The problem asks us to calculate the total number of ways to distribute n candies among exactly three children, with the constraint that no child can receive more than limit candies. Essentially, we are asked to enumerate all possible triplets (a, b, c) of non-negative integers that satisfy two conditions: a + b + c = n and 0 <= a, b, c <= limit. The output is the count of all such valid triplets.

The inputs are two positive integers. n represents the total number of candies available, which can be as large as 1,000,000. limit represents the maximum number of candies a single child can receive, which can also be as large as 1,000,000. These constraints imply that a naive enumeration of all possible combinations for large n would be computationally expensive.

Important edge cases include when n is very small (e.g., 1, 2, 3), when limit is smaller than n (forcing the distribution to respect the limit), or when limit is larger than n (allowing some children to receive zero candies). The problem guarantees that both inputs are positive integers, so we do not have to handle negative numbers or zero candies.

Approaches

Brute Force Approach

The brute-force solution involves iterating over all possible values for the first child from 0 to min(n, limit), for the second child also from 0 to min(n, limit), and calculating the third child's candies as n - a - b. If the third child’s value is non-negative and less than or equal to limit, the triplet is valid. We would count all such triplets.

This approach is correct because it explicitly enumerates all possibilities, but it has a worst-case time complexity of O(limit^2), which is too slow for the upper bounds of the problem (n and limit up to 1,000,000).

Optimal Approach

The key observation for optimization is that the number of valid triplets for a given a and b can be computed directly without iterating over c. Since c = n - a - b must satisfy 0 <= c <= limit, we know that for fixed a, b must lie in the range [max(0, n - limit - a), min(limit, n - a)]. Counting the number of integers in this range gives the number of valid b values for that a. Summing over all valid a values produces the total count.

This reduces the complexity from O(limit^2) to O(limit), which is acceptable given the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(limit^2) O(1) Enumerate all triplets explicitly
Optimal O(limit) O(1) Use range calculation for b based on a to count valid triplets

Algorithm Walkthrough

  1. Initialize a counter total_ways to zero.
  2. Loop over a from 0 to min(n, limit). This represents the number of candies given to the first child.
  3. For each a, compute the valid range of b using b_min = max(0, n - limit - a) and b_max = min(limit, n - a). This ensures that c = n - a - b is non-negative and does not exceed limit.
  4. If b_min <= b_max, increment total_ways by b_max - b_min + 1, which is the number of valid b values for the current a.
  5. After iterating all a, return total_ways.

Why it works: The algorithm systematically counts all valid (a, b, c) triplets without iterating over c. For each a, it computes exactly how many b values lead to a valid c. The invariant is that for each iteration, all triplets counted satisfy both the total candy requirement and the per-child limit.

Python Solution

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        total_ways = 0
        for a in range(min(n, limit) + 1):
            b_min = max(0, n - limit - a)
            b_max = min(limit, n - a)
            if b_min <= b_max:
                total_ways += b_max - b_min + 1
        return total_ways

This implementation follows the optimal algorithm. We loop over all possible a values and compute the valid range of b that ensures c stays within bounds. For each a, the number of valid b values is added to total_ways. Finally, we return the accumulated total.

Go Solution

func distributeCandies(n int, limit int) int64 {
    var totalWays int64 = 0
    maxA := n
    if limit < n {
        maxA = limit
    }
    for a := 0; a <= maxA; a++ {
        bMin := 0
        if n-limit-a > 0 {
            bMin = n - limit - a
        }
        bMax := n - a
        if bMax > limit {
            bMax = limit
        }
        if bMin <= bMax {
            totalWays += int64(bMax - bMin + 1)
        }
    }
    return totalWays
}

The Go version mirrors the Python approach. We explicitly handle integer arithmetic and cast the range difference to int64 to prevent overflow. Go does not need dynamic typing, so we compute the range using explicit max/min operations.

Worked Examples

Example 1: n = 5, limit = 2

a b_min b_max valid b count total_ways
0 3 2 0 0
1 2 2 1 1
2 1 2 2 3

Output: 3

Example 2: n = 3, limit = 3

a b_min b_max valid b count total_ways
0 0 3 4 4
1 0 2 3 7
2 0 1 2 9
3 0 0 1 10

Output: 10

Complexity Analysis

Measure Complexity Explanation
Time O(min(n, limit)) Loop over a from 0 to min(n, limit)
Space O(1) Only a few integer variables are used, no extra data structures

The loop over a is bounded by min(n, limit), and the computation for each a is constant time. Memory usage is minimal and does not scale with input.

Test Cases

# Provided examples
assert Solution().distributeCandies(5, 2) == 3  # Example 1
assert Solution().distributeCandies(3, 3) == 10  # Example 2

# Edge and boundary cases
assert Solution().distributeCandies(1, 1) == 1  # Only (1,0,0) permutations
assert Solution().distributeCandies(0, 1) == 1  # Only (0,0,0)
assert Solution().distributeCandies(6, 2) == 7  # Max per child is 2
assert Solution().distributeCandies(1000000, 1) == 0  # Cannot distribute more than limit
assert Solution().distributeCandies(3, 1000000) == 10  # Large limit, n small
Test Why
n=5, limit=2 Checks normal small case with limit restricting distribution
n=3, limit=3 Checks normal small case with limit not restrictive
n=1, limit=1 Smallest positive n
n=0, limit=1 No candies to distribute
n=6, limit=2 Cannot assign more than limit to any child
n=1000000, limit=1 Stress test, no solution possible
n=3, limit=1000000 Large limit, small n, should count all combinations

Edge Cases

One important edge case is when n is smaller than limit. In this case, the upper bound for each child is not restrictive, so we need to count all non-negative integer solutions summing to n. The algorithm correctly handles this because b_max is capped by min(limit, n-a).

Another edge case is when limit is smaller than n/3. This can make it impossible to distribute all candies evenly. The algorithm accounts for this by calculating b_min = max(0, n-limit-a), ensuring c does not exceed the limit.

A third edge case is when n is