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 I

Number: 3199

Difficulty: Easy

Paid? No

Companies: Amazon, Rubrik

Problem Description

Given n candies and 3 children, the goal is to count the total number of ways to distribute the candies such that no child gets more than a specified number (limit) of candies. Each distribution is represented as a triple (a, b, c) with a + b + c = n and each of a, b, c falls in the range [0, limit].

Key Insights

  • The distribution must satisfy a + b + c = n and each child receives between 0 and limit candies.
  • A brute force approach iterates over all possibilities for two children and determines the third child's candies by subtraction.
  • The problem size is small (n, limit ≤ 50), so a double loop (or triple loop) approach is computationally feasible.
  • Checking the constraint for the third child is critical to ensure the distribution is valid.

Space and Time Complexity

Time Complexity: O(limit^2) – iterating over two children and computing the third in constant time. Space Complexity: O(1) – constant extra space used.

Solution

The solution uses a nested iteration approach where:

  1. Loop through all possible values for the first child's candies from 0 to limit.
  2. For each possibility, loop through all possible values for the second child's candies from 0 to limit.
  3. Compute the third child's candies as n minus the sum of the first two.
  4. Check if the third child's candy count is valid (i.e., between 0 and limit).
  5. Count each valid distribution.

This approach directly enumerates all valid assignments ensuring all constraints are met.

Code Solutions

def distribute_candies(n, limit):
    count = 0
    # Iterate over possible candies for the first child
    for a in range(limit + 1):
        # Iterate over possible candies for the second child
        for b in range(limit + 1):
            c = n - (a + b)  # Compute the candies for the third child
            # Check if the third child's candies are within the allowed limit
            if 0 <= c <= limit:
                count += 1
    return count

# Example usage
if __name__ == "__main__":
    print(distribute_candies(5, 2))  # Expected output: 3
    print(distribute_candies(3, 3))  # Expected output: 10
← Back to All Questions