LeetCode 2928 - Distribute Candies Among Children I

The problem asks us to calculate the number of ways to distribute n candies among exactly three children such that no child receives more than a specified limit of candies.

leetcodeeasymathcombinatoricsenumeration

LeetCode Problem 2928

Difficulty: 🟢 Easy
Topics: Math, Combinatorics, Enumeration

Solution

Problem Understanding

The problem asks us to calculate the number of ways to distribute n candies among exactly three children such that no child receives more than a specified limit of candies. In other words, we are looking for all integer triplets (a, b, c) such that a + b + c = n and each of a, b, and c satisfies 0 <= a, b, c <= limit.

The input consists of two integers: n, representing the total candies, and limit, representing the maximum candies any child can receive. The output is a single integer representing the count of all valid distributions. The constraints 1 <= n <= 50 and 1 <= limit <= 50 indicate that the search space is small enough to consider combinatorial or enumerative approaches.

Edge cases to consider include situations where n is less than limit, n is exactly 3 * limit, or n is very small such as 1, which restricts the range of possible distributions. The problem guarantees positive integers, so we do not need to handle negative or zero inputs.

Approaches

The brute-force approach is straightforward: iterate over all possible values for the first child a from 0 to limit, for the second child b from 0 to limit, and compute the third child c = n - a - b. If c also falls within [0, limit], count this distribution. This approach is correct but can be slightly inefficient because it checks some combinations that are guaranteed to be invalid when a + b > n.

A more optimal approach uses mathematical reasoning. For each possible value of a from 0 to min(n, limit), we compute valid ranges for b such that 0 <= b <= min(limit, n - a) and c = n - a - b remains within [0, limit]. Instead of iterating over b, we can count the number of valid b values directly using the formula max(0, min(limit, n - a) - max(0, n - a - limit) + 1). This avoids the innermost loop and improves efficiency.

Approach Time Complexity Space Complexity Notes
Brute Force O(limit^2) O(1) Iterate over a and b, check c.
Optimal O(limit) O(1) Iterate only over a, compute valid b count mathematically.

Algorithm Walkthrough

  1. Initialize a variable count to store the total number of valid distributions.
  2. Iterate a from 0 to min(n, limit). This ensures we never exceed the total candies or the per-child limit.
  3. For each a, compute the minimum and maximum valid values of b such that c = n - a - b stays within [0, limit]. The minimum valid b is max(0, n - a - limit) and the maximum valid b is min(limit, n - a).
  4. If the minimum valid b is less than or equal to the maximum valid b, the number of valid b values is max_b - min_b + 1. Add this to count.
  5. After the loop completes, return count as the total number of distributions.

Why it works: The algorithm ensures that for every fixed a, all valid values of b produce a c that satisfies the constraints. This covers all combinations without missing or double-counting any possibilities.

Python Solution

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

This implementation iterates over all possible a values, calculates the valid range for b, and directly counts the number of valid b values. This avoids unnecessary loops and ensures correctness for all constraints.

Go Solution

func distributeCandies(n int, limit int) int {
    count := 0
    for a := 0; a <= min(n, limit); a++ {
        minB := max(0, n-a-limit)
        maxB := min(limit, n-a)
        if minB <= maxB {
            count += maxB - minB + 1
        }
    }
    return count
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go solution mirrors the Python solution. We define helper functions min and max to calculate bounds for b. Counting is done using arithmetic instead of a nested loop to improve efficiency.

Worked Examples

Example 1: n = 5, limit = 2

a min_b max_b valid b values count
0 3 2 none 0
1 2 2 2 1
2 1 2 1, 2 2

Total count = 3

Example 2: n = 3, limit = 3

a min_b max_b valid b values count
0 0 3 0,1,2,3 4
1 0 2 0,1,2 3
2 0 1 0,1 2
3 0 0 0 1

Total count = 10

Complexity Analysis

Measure Complexity Explanation
Time O(limit) We iterate over a from 0 to min(n, limit) and compute valid b counts mathematically, no nested loops.
Space O(1) Only a few integer variables are used; no extra data structures are needed.

The reasoning is that by converting the innermost loop into an arithmetic calculation, we reduce the time complexity from quadratic to linear with respect to limit.

Test Cases

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

# Edge cases
assert Solution().distributeCandies(1, 1) == 1  # smallest n and limit
assert Solution().distributeCandies(50, 50) == 1326  # largest n and limit
assert Solution().distributeCandies(50, 1) == 0  # limit too small to reach n
assert Solution().distributeCandies(0, 5) == 1  # zero candies, only (0,0,0)
Test Why
n=5, limit=2 verifies basic counting for small numbers
n=3, limit=3 verifies multiple combinations including zero
n=1, limit=1 verifies minimum input
n=50, limit=50 stress test for upper limit
n=50, limit=1 verifies scenario where limit < average required per child
n=0, limit=5 verifies edge case of zero candies

Edge Cases

  1. Zero candies (n = 0): There is only one valid distribution (0, 0, 0). The implementation correctly handles this because the range calculations for b will yield exactly one valid value.
  2. Limit smaller than needed per child: For example, n = 50 and limit = 1. The algorithm calculates valid b ranges and finds none, correctly returning 0 distributions.
  3. Limit larger than total candies: For instance, n = 3, limit = 5. The algorithm correctly computes ranges for b and c without exceeding the total n, so no invalid combinations are counted.

This approach systematically handles all boundary conditions without special casing.