2226. Maximum Candies Allocated to K Children - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given a 0-indexed array candies where each element represents a pile of candies of that size. You can split any pile into any number of smaller sub-piles, but you cannot merge candies from different piles. You are also given an integer k (number of children). We want to distribute candy piles to these k children so that each child gets the same number of candies (each child takes candies from only one original pile, and some piles may be left unused). Return the maximum number of candies each child can get.

Example 1:
Input: candies = [5, 8, 6], k = 3
Output: 5
Explanation: Split the pile of 8 into [5, 3] and the pile of 6 into [5, 1]. Now we have piles of sizes [5, 5, 3, 5, 1]. We can give three piles of size 5 to 3 children, so each child gets 5 candies. It’s impossible for each child to get more than 5.
Example 2:
Input: candies = [2, 5], k = 11
Output: 0
Explanation: There are 7 candies total which is less than 11, so it’s impossible to give each of the 11 children even one candy. Thus, the answer is 0.
Example 3:
Input: candies = [5, 8, 6], k = 4
Output: 4
Explanation: Total candies = 19 for 4 kids. We cannot give 5 each (that would require 20 candies). However, we can give 4 candies to each child by splitting: for example, split 8 into [4,4], 6 into [4,2], and 5 into [4,1]. This yields four piles of 4, which can go to the 4 children. So each child gets 4.

Constraints: 1 <= candies.length <= 10^5, 1 <= candies[i] <= 10^7, 1 <= k <= 10^12 . This means we can have up to 100k piles and up to 1 trillion children, so an efficient solution is needed.

Hints

Feasibility Check: If you guess a number X candies per child, how can you check if it’s possible to achieve? Consider splitting each pile into sub-piles of size X (you’ll get pile // X pieces from a pile). How many children can be fed this way?
Monotonic Condition: Notice that if it’s possible for each child to get X candies, it will also be possible for any smaller number of candies (if you can give everyone X, giving everyone X-1 is easier). This monotonic property hints that binary search could be a good approach to find the maximum feasible X.
Edge Insight: What is the upper bound for X? Each child can’t get more candies than the size of the largest pile (since one child’s candies must come from a single original pile). Also, if the total candies is less than k, the answer must be 0.

Multiple Approaches

1. Brute Force (Linear Search)

A straightforward idea is to try all possible values of candies per child from 1 up to some maximum and check each. We could start from 1 candy each and increase, or start from the theoretical upper bound and decrease until it’s possible. For each candidate X, we sum up how many children we can satisfy: count = sum(candies[i] // X for each pile i). If count >= k, then X is achievable (we can satisfy at least k children with X candies each); otherwise it’s not. We would find the largest X that works.

Why it’s not efficient: The maximum X to check could be as high as the largest pile (up to 10^7). Trying each value from 1 to 10^7 and doing a division for up to 100,000 piles each time would be billions of operations in the worst case (~10^7 * 10^5 = 10^12 checks), which is far too slow.

This brute force approach is conceptually simple but will not work within the problem’s constraints due to its extremely high time complexity.

2. Optimal Approach (Binary Search)

We can optimize by using binary search to find the maximum feasible candies per child. The idea is to search the answer space (0 to max pile size) instead of checking every value. We leverage the monotonic property: if a certain number X candies each is possible, then anything less than X is also possible, and if X is not possible, anything greater than X won’t be possible either.

How to apply binary search:

Search Range: Set low = 0 and high = max(candies). (We include 0 in case it’s impossible to give even 1 candy each, as in Example 2.) We could also use high = sum(candies)//k as an initial upper bound, but using the max pile size is simpler and safe.
Mid Calculation: Pick mid = (low + high) // 2 (or the upper mid if using a bias to avoid infinite loop, e.g. (low + high + 1)//2). This mid represents a candidate number of candies per child.
Feasibility Check: Compute how many children can get mid candies using all piles: count = sum(candies[i] // mid for all i). Each pile i can supply at most candies[i] // mid children with mid candies (by splitting that pile into that many sub-piles of size mid). Then:
- If count >= k, it means we can satisfy at least k children with mid candies each, so mid is feasible. We record this as a possible answer and try to increase low (search right half) to see if a larger X works.
- If count < k, it means mid candies each is too high (not enough total pieces for all k kids), so we decrease high (search left half) to try a smaller number.
We continue the binary search until low > high or until the range narrows down. The maximum feasible value will be the answer.

This approach efficiently zeroes in on the solution by cutting the search space in half each time, rather than linear scanning. The feasibility check (sum(candies[i] // mid)) is O(n) for each mid, and we will do about log2(max_candies) iterations.

Code Implementation

Below are implementations in Python and Java using the binary search approach. Both include a simple main method to demonstrate usage with the given examples.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Brute Force Approach: Checking every possible candies-per-child from 1 up to M (max pile size) gives a time complexity around O(n * M) in the worst case. With n up to 10^5 and M up to 10^7, this is about 10^12 operations, which is not feasible. Space complexity is O(1) extra (we just use counters).
Binary Search Approach: We perform a binary search on the answer range [0, M]. Each check (for a given mid value) iterates through all n piles to compute the count, which is O(n). We do at most O(log M) iterations of binary search. Thus time complexity is O(n * log M). With n = 10^5 and M ≈ 10^7, log2(10^7) ≈ 24, so roughly 2.4 million operations, which is efficient. Space complexity is O(1) extra, since we only use a few integer/long variables for the search (the input array itself is given).

In our case, M = max(candies). Another upper bound for the search is total_candies//k (average candies per child if candies could be pooled), but using max(candies) is a simpler bound for analysis. The binary search will correctly converge to the maximum feasible value.

Step-by-Step Walkthrough with Visuals

Let’s walk through the optimal binary search solution using Example 1 (candies = [5,8,6], k = 3). Total candies = 19, max pile = 8. The possible answer X lies between 0 and 8. We use binary search to find the largest X such that at least 3 children can get X candies each:

Initial range: low = 1, high = 8. (We start at 1 because 0 is trivially always possible, and high is 8 from the largest pile.)
First guess: mid = (1+8)//2 = 4. Check if each child can get 4 candies:
- Pile 5 can give ⌊5/4⌋ = 1 child 4 candies.
- Pile 8 can give ⌊8/4⌋ = 2 children 4 candies each.
- Pile 6 can give ⌊6/4⌋ = 1 child 4 candies.
- Total children we can satisfy with 4 candies each = 1+2+1 = 4. This is ≥ k (3), so 4 candies each is possible. We record X=4 as a valid answer and try to increase the lower bound to find a higher number. Set low = 5 (mid + 1) to search higher.
Second guess: Now low = 5, high = 8, so mid = (5+8)//2 = 6. Check 6 candies per child:
- Pile 5 can give ⌊5/6⌋ = 0 children (5 is not enough to give 6 to even one child).
- Pile 8 can give ⌊8/6⌋ = 1 child 6 candies.
- Pile 6 can give ⌊6/6⌋ = 1 child 6 candies.
- Total children with 6 each = 0+1+1 = 2. This is < k (3), so 6 each is not possible (we don’t have enough pieces to cover all 3 children). We need to try a smaller number. Set high = 5 (mid - 1).
Third guess: Now low = 5, high = 5, so mid = 5. Check 5 candies per child:
- Pile 5 can give ⌊5/5⌋ = 1 child 5 candies.
- Pile 8 can give ⌊8/5⌋ = 1 child 5 candies.
- Pile 6 can give ⌊6/5⌋ = 1 child 5 candies.
- Total children with 5 each = 1+1+1 = 3, which is exactly k. So 5 each is possible (just enough). We record X=5 and set low = 6 to try for a larger value.
Now low = 6 and high = 5 – the range has inverted, which means the binary search is done. The last known feasible value was 5. Therefore, the answer is 5.

The table below summarizes the checks:

Guess X	Children served (sum of ⌊pile/X⌋)	Feasible?
4	4 (from piles: 1+2+1)	Yes (≥3)
6	2 (from piles: 0+1+1)	No (<3)
5	3 (from piles: 1+1+1)	Yes (≥3)

We found that 5 is the maximum X such that we can serve at least 3 children. This matches the expected result. The binary search efficiently homes in on the correct value in only a few steps instead of testing every possibility.

Common Mistakes & Edge Cases

Combining Piles: A frequent misunderstanding is to try to combine multiple piles for one child. Remember, each child’s candies must come from a single original pile (though that pile can be split into pieces). You cannot add two smaller piles from different origins to give one child more candies. If you mistakenly combine piles, you might overestimate feasibility.
Not Handling Zero Result: If the total number of candies is less than k, it’s impossible to give each child even one candy. The correct output in such cases is 0 (as in Example 2). Ensure your code handles this scenario, otherwise a binary search might misbehave (e.g., dividing by zero if not handled, or ending up returning 1 when it should be 0).
Off-by-One in Binary Search: Implementing binary search can be tricky. Make sure to choose the mid-point and update bounds correctly. One common bug is an infinite loop if low is not properly adjusted. In this problem, using low = mid + 1 when feasible and high = mid - 1 when not, or equivalently using the pattern with mid = (low + high + 1)//2, will correctly converge. Always test your binary search on edge cases like when k is 1 or very large.
Data Type Overflow: In languages like Java, be careful with data types. The sum of candies or the value of k can exceed the range of 32-bit int. Use a larger type (e.g., long in Java) for summing and comparisons to avoid overflow issues when k is up to 10^12.
Edge cases to consider:
- k larger than total candies → result 0 (no one gets any candy).
- k = 1 → result is simply the size of the largest pile (one child can take the biggest pile, since they can't combine piles).
- candies has one pile (then if that one pile has ≥k candies, each child can get at most ⌊pile/k⌋; if k is 1, answer is the whole pile; if k is more than 1, you effectively split that one pile among all children).
- Very large k (e.g., 10^12) with many piles: make sure your loop breaks when count exceeds k to avoid unnecessary summing (as we did in code) since sum of floors could be huge but we only care if it’s ≥k.

This problem is a form of “fair allocation” or “splitting” problem using binary search. Here are a few related problems and variations to practice:

Cutting Ribbons (LeetCode 1891): You have ribbon lengths and want to cut them into at least k pieces of equal length. You need to find the maximum possible length of each piece. This is almost the same problem pattern: use binary search to maximize the length of pieces (analogous to candies per child).
Koko Eating Bananas (LeetCode 875): Koko the monkey has to eat all bananas in H hours. She can eat at most K bananas per hour (from a single pile each hour). You must find the minimum speed K such that all bananas can be eaten in time. This is a minimization version of a similar idea, solved with binary search on the eating speed.
Capacity to Ship Packages in D Days (LeetCode 1011): You have weights of packages and need to find the smallest ship capacity to ship them within D days. You decide if a given capacity is sufficient by simulating day-by-day loading. It’s another problem where binary search on an answer (capacity) is used with a feasibility check.
Split Array Largest Sum (LeetCode 410): Divide an array into m subarrays to minimize the largest sum among them. This can be solved via binary search on the potential largest sum and checking if a split is possible within m subarrays. It’s a partition problem with a greedy check, related by the binary search technique on the answer space.