We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distribute Candies Among Children II

Number: 3201

Difficulty: Medium

Paid? No

Companies: Amazon, Rubrik

Problem Description

Given two positive integers n and limit, count the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies. A child may receive 0 candies, and the order matters (distributions are considered different even if they consist of the same numbers in a different order).

Key Insights

  • Without restrictions, the number of nonnegative integer solutions to x + y + z = n is C(n+2, 2).
  • The constraint “no child gets more than limit” is handled by counting and subtracting the distributions where one or more children exceed the limit.
  • Use the inclusion-exclusion principle: subtract the cases where one child receives more than limit candies, add back the cases where two children exceed the limit, and subtract the (rare) case where all three children exceed the limit.
  • Each time a child is forced over the limit, substitute a variable: for a child getting > limit candies, let that child receive limit+1 + a′, and adjust the sum accordingly.
  • Since the number of children is fixed (3), the summation in the inclusion-exclusion is constant time.

Space and Time Complexity

Time Complexity: O(1) – We only sum a constant number of terms (k = 0 to 3). Space Complexity: O(1) – Only a constant amount of memory is used, regardless of n or limit.

Solution

We first calculate the total number of solutions to x + y + z = n with x, y, z >= 0 using the combinatorial formula C(n+2, 2). Next, to enforce the condition that no child gets more than limit candies, we subtract the number of distributions where at least one child receives more than limit candies. For every child that exceeds the limit, we define a new variable representing the excess amount (over limit+1) and adjust the target sum accordingly.

Using inclusion‐exclusion: Total Ways = ∑ (from k = 0 to 3) [(-1)^k * C(3, k) * C(n - k*(limit+1)+2, 2)] where each term is included only if n - k*(limit+1) ≥ 0. This formula correctly adds and subtracts the cases where 1, 2, or 3 children exceed the limit.

Key data structures: No complex data structures are needed. The algorithm employs mathematical combinations (binomial coefficients), computed directly with formulas.

Code Solutions

# Python solution with line-by-line comments

def nCr2(x):
    # Compute combination C(x, 2) = x*(x-1)/2
    # For valid combinations, x must be at least 2
    if x < 2:
        return 0
    return (x * (x - 1)) // 2

def count_distributions(n, limit):
    total = 0
    # Inclusion-Exclusion: try k = 0,1,2,3 children exceeding the limit.
    for k in range(4):  # since there are 3 children, maximum k is 3
        # check if remaining candies n - k*(limit+1) is non-negative
        remaining = n - k * (limit + 1)
        if remaining < 0:
            continue
        # number of solutions for remaining candies: C(remaining+2, 2)
        ways = nCr2(remaining + 2)
        # add or subtract based on inclusion-exclusion sign and count (C(3,k))
        # C(3,k) is computed as: 1 if k==0, 3 if k==1, 3 if k==2, 1 if k==3.
        from math import comb
        total += ((-1) ** k) * comb(3, k) * ways
    return total

# Example usage:
print(count_distributions(5, 2))  # Expected output: 3
print(count_distributions(3, 3))  # Expected output: 10
← Back to All Questions