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

Maximum Candies Allocated to K Children

Number: 1335

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft, Oracle, TikTok

Problem Description

Given an array of candy piles where each element represents the number of candies in that pile, you can split each pile into any number of smaller sub-piles. You need to distribute these sub-piles to k children such that each child receives the same number of candies and all candies for a child come from only one original pile. Determine the maximum number of candies each child can get.

Key Insights

  • Use binary search on the answer space (the possible number of candies per child).
  • For each candidate number of candies, determine if it is possible to form at least k sub-piles (using floor division on each pile).
  • The feasibility check is monotonic: if you can distribute x candies per child, then any value lower than x is also possible.
  • The search space is between 1 and the maximum number in the candies array.

Space and Time Complexity

Time Complexity: O(n * log(max(candies))) where n is the number of piles. Space Complexity: O(1)

Solution

We solve the problem using binary search over the candidate answer space. For each candidate value mid (the number of candies per child), we determine if we can obtain at least k sub-piles by summing up floor(candy / mid) for every pile in the input array. Depending on the feasibility, we adjust our search range. This approach guarantees an efficient solution even when the input size is large.

Code Solutions

Below are code solutions in multiple languages with inline comments:

# Python solution
def maximumCandies(candies, k):
    # Define a helper function that checks if it's possible to form at least k piles of size x
    def canDistribute(x):
        count = 0
        for pile in candies:
            count += pile // x  # Number of piles from this pile of size x
            if count >= k:
                return True
        return False

    # Set up binary search between 1 and the maximum number of candies in any pile.
    low, high = 1, max(candies)
    ans = 0
    while low <= high:
        mid = (low + high) // 2  # Candidate for maximum candies per child
        if canDistribute(mid):
            ans = mid         # Found a valid candidate, try for a higher value
            low = mid + 1
        else:
            high = mid - 1    # Too many candies required per child, try lower value
    return ans

# Example usage
print(maximumCandies([5, 8, 6], 3))  # Output: 5
← Back to All Questions