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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Distribute Candies Among Children I

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem can be visualized as finding non-negative integer solutions to the equation x1 + x2 + x3 = n, with the constraint that 0 ≤ xi ≤ limit for each child i.
  • The maximum number of candies any child can receive is capped by the limit, which affects the distribution options.
  • Using combinatorial methods, we can compute the number of valid distributions by iterating through possible values for one child and calculating the remaining candies for the other two.

Space and Time Complexity

Time Complexity: O(limit^2)
Space Complexity: O(1)

Solution

To solve this problem, we use a combinatorial approach. We iterate over the number of candies assigned to the first child (from 0 to the minimum of limit and n). For each allocation to the first child, we calculate the remaining candies that need to be distributed to the other two children. We then count the number of ways to distribute those remaining candies without exceeding the limit for each child.

We can use the formula for combinations to find the number of ways to allocate the remaining candies, but given the constraints, we can use a simple nested loop to iterate through possible distributions.

Code Solutions

def distribute_candies(n: int, limit: int) -> int:
    count = 0
    for i in range(min(limit, n) + 1):  # First child's candies
        for j in range(min(limit, n - i) + 1):  # Second child's candies
            k = n - i - j  # Remaining candies for third child
            if 0 <= k <= limit:  # Check if third child is within limit
                count += 1
    return count
← Back to All Questions