Watch 10 video solutions for Maximum Candies Allocated to K Children, a medium level problem involving Array, Binary Search. This walkthrough by NeetCodeIO has 11,139 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.
You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.
Return the maximum number of candies each child can get.
Example 1:
Input: candies = [5,8,6], k = 3 Output: 5 Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.
Example 2:
Input: candies = [2,5], k = 11 Output: 0 Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.
Constraints:
1 <= candies.length <= 1051 <= candies[i] <= 1071 <= k <= 1012Problem Overview: You receive an array candies where each element represents a pile of candies. You can split a pile into smaller piles but cannot combine piles. The goal is to distribute candies to k children so every child receives the same number of candies. Return the maximum candies each child can get.
Approach 1: Brute Force Enumeration (Time: O(n * M), Space: O(1))
A direct approach is to try every possible number of candies per child from 1 up to the largest pile size M. For each candidate value x, iterate through the array and compute how many children can be served using pile // x. If the total count is at least k, the distribution works. Track the largest valid x. This approach performs a full array scan for every possible candy count, which becomes too slow when the maximum pile value is large.
Approach 2: Binary Search on Answer (Time: O(n log M), Space: O(1))
The key observation: if you can give x candies per child, then any value smaller than x is also feasible. This monotonic property makes the problem ideal for binary search. Instead of testing every possible value, search the range [1, max(candies)]. For each midpoint mid, iterate through the array and compute how many children can be served using pile // mid. If the total number of children served is at least k, increase the lower bound to search for a larger answer. Otherwise reduce the upper bound.
The counting step is straightforward: loop through the array and accumulate pile // mid. This represents how many equal portions of size mid each pile can contribute. The algorithm repeatedly narrows the search space until the largest feasible value is found.
This method avoids scanning every possible candy amount. Instead, it performs roughly log(max(candies)) checks, each requiring a single pass through the array. With large pile sizes (up to millions or billions), this improvement is substantial.
Recommended for interviews: Binary search on the answer is the expected solution. Interviewers look for recognition of the monotonic feasibility condition and the ability to convert the problem into a search space over possible answers. Mentioning the brute force approach first shows understanding of the constraint, while the binary search optimization demonstrates strong algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * M) | O(1) | Conceptual baseline or when maximum pile size is very small |
| Binary Search on Answer | O(n log M) | O(1) | Optimal solution for large arrays and large pile values |