LeetCode 2226 - Maximum Candies Allocated to K Children

This problem asks us to determine the largest number of candies that every child can receive equally, given a collection of candy piles and a number of children k. We are given an integer array candies, where candies[i] represents the size of the i-th pile.

leetcodemediumarraybinary-search

LeetCode Problem 2226

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

This problem asks us to determine the largest number of candies that every child can receive equally, given a collection of candy piles and a number of children k.

We are given an integer array candies, where candies[i] represents the size of the i-th pile. We are allowed to split a pile into smaller sub-piles, but we are not allowed to combine candies from different piles. This restriction is very important because it means each child must receive all of their candies from a single pile or sub-pile.

The goal is to distribute candies to exactly k children such that:

  1. Every child receives the same number of candies.
  2. Each child receives candies from only one pile.
  3. Piles may be divided into multiple smaller piles.
  4. Some piles may remain unused.

We want to maximize the number of candies each child receives.

For example, if we try to give every child x candies, then each pile contributes:

$$\left\lfloor \frac{\text{pile size}}{x} \right\rfloor$$

children, because a pile of size 8 can produce 2 groups of size 4, or 1 group of size 5, and so on.

The constraints are particularly important:

  • candies.length <= 10^5
  • candies[i] <= 10^7
  • k <= 10^12

A naive simulation would be far too slow because the search space for the answer can be as large as 10^7, and there may be 10^5 piles. This strongly suggests that we need something more efficient than testing every possible candy count individually.

An important observation is that the answer is bounded:

  • The minimum possible answer is 0.
  • The maximum possible answer cannot exceed the largest pile size.

There are several edge cases to consider upfront. If the total number of candies is less than k, then it is impossible to give even one candy per child, so the answer must be 0. Another tricky case occurs when there is only one pile, since all children must come from splits of that single pile. Extremely large values of k, up to 10^12, also mean we must avoid algorithms proportional to k.

Approaches

Brute Force Approach

A straightforward solution would be to try every possible candy count per child from 1 up to max(candies).

For each candidate amount x, we compute how many children can be served:

$$\sum \left\lfloor \frac{\text{candies}[i]}{x} \right\rfloor$$

If the total is at least k, then x is feasible. Otherwise, it is not.

We would keep track of the largest feasible value.

This approach is correct because it exhaustively checks every possible answer and selects the maximum valid one. However, it is far too slow for the problem constraints.

Suppose:

  • max(candies) = 10^7
  • n = 10^5

Then the complexity becomes:

$$O(n \cdot \max(candies))$$

which could reach:

$$10^5 \times 10^7 = 10^{12}$$

operations, clearly infeasible.

Key Insight: Binary Search on the Answer

The key observation is that this problem has a monotonic property.

If it is possible to give every child x candies, then it is also possible to give every child any smaller value than x.

For example:

  • If 5 candies per child works, then 4, 3, 2, and 1 will also work.
  • If 5 does not work, then 6, 7, and larger values also cannot work.

This creates a monotonic search space:

feasible feasible feasible feasible infeasible infeasible

Whenever we have a monotonic condition, binary search becomes applicable.

Instead of checking every possible answer, we binary search over the range:

$$[1, \max(candies)]$$

For each midpoint mid, we calculate how many children can receive mid candies.

  • If at least k children can be served, then mid is feasible, and we try larger values.
  • Otherwise, mid is too large, so we try smaller values.

This reduces the search dramatically.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × max(candies)) O(1) Checks every possible candy count
Optimal O(n log(max(candies))) O(1) Uses binary search on the answer space

Algorithm Walkthrough

  1. Compute the maximum pile size.

Since no child can receive more candies than the largest pile, this becomes the upper bound of our search range. 2. Initialize the binary search range.

Set:

  • left = 1
  • right = max(candies)

We start from 1 because distributing 0 candies is trivial and only needed if no valid positive answer exists. 3. Perform binary search.

While left <= right:

  • Compute the middle value:

$$mid = (left + right) // 2$$

This represents a candidate number of candies per child. 4. Count how many children can be served.

For each pile:

$$\text{pile} // mid$$

tells us how many sub-piles of size mid can be created.

Sum these values across all piles. 5. Check feasibility.

If the total number of children served is at least k:

  • mid is feasible.
  • Record it as a candidate answer.
  • Search for a larger value:
left = mid + 1

Otherwise:

  • mid is too large.
  • Search smaller values:
right = mid - 1
  1. Return the result.

The binary search eventually converges to the largest feasible candy count.

Why it works

The correctness relies on the monotonic property of feasibility. If x candies per child is achievable, then any smaller value is also achievable because we can always split piles into smaller groups. Conversely, if x is impossible, any larger value is impossible as well. Binary search correctly finds the boundary between feasible and infeasible values, guaranteeing that the maximum valid answer is returned.

Python Solution

from typing import List

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        left = 1
        right = max(candies)
        answer = 0

        while left <= right:
            mid = (left + right) // 2

            children_served = 0
            for pile in candies:
                children_served += pile // mid

            if children_served >= k:
                answer = mid
                left = mid + 1
            else:
                right = mid - 1

        return answer

The implementation directly follows the binary search strategy described earlier.

We begin by establishing the search range. The smallest meaningful value is 1, while the largest possible answer is the largest pile size.

Inside the binary search loop, mid represents a candidate amount of candies per child. We then iterate through every pile and compute how many children can receive mid candies from that pile using integer division.

If the total number of children served is at least k, then the candidate value is feasible. We record it in answer and continue searching toward larger values because we want the maximum possible distribution.

If fewer than k children can be served, then mid is too large, and we shrink the search space toward smaller values.

Once the search terminates, answer contains the maximum feasible candy count.

Go Solution

func maximumCandies(candies []int, k int64) int {
	left := 1
	right := 0

	for _, pile := range candies {
		if pile > right {
			right = pile
		}
	}

	answer := 0

	for left <= right {
		mid := left + (right-left)/2

		var childrenServed int64 = 0

		for _, pile := range candies {
			childrenServed += int64(pile / mid)
		}

		if childrenServed >= k {
			answer = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version, with a few language-specific considerations.

Since k can be as large as 10^12, we use int64 when counting childrenServed. Using a standard int could risk overflow on some systems.

The midpoint calculation uses:

mid := left + (right-left)/2

instead of (left + right) / 2 to avoid potential integer overflow, even though the bounds are safe in this problem.

Go slices are naturally used for iterating through the candy piles, and no additional memory structures are required.

Worked Examples

Example 1

candies = [5, 8, 6]
k = 3

Search range:

left = 1
right = 8
Iteration left right mid Children Served Feasible? Action
1 1 8 4 1 + 2 + 1 = 4 Yes Try larger
2 5 8 6 0 + 1 + 1 = 2 No Try smaller
3 5 5 5 1 + 1 + 1 = 3 Yes Try larger

After iteration 3:

left = 6
right = 5

The search stops.

Final answer:

5

Example 2

candies = [2, 5]
k = 11

Search range:

left = 1
right = 5
Iteration left right mid Children Served Feasible? Action
1 1 5 3 0 + 1 = 1 No Try smaller
2 1 2 1 2 + 5 = 7 No Try smaller

Now:

left = 1
right = 0

No feasible positive answer exists.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log(max(candies))) Binary search performs log(max(candies)) iterations, each scanning all piles
Space O(1) Only a few variables are used

The binary search range spans from 1 to max(candies), giving approximately:

$$\log_2(\max(candies))$$

iterations. Since each iteration scans the entire candies array of size n, the total complexity becomes:

$$O(n \log(\max(candies)))$$

Given max(candies) <= 10^7, the logarithmic factor is very small, roughly 24 iterations, making this solution highly efficient.

Test Cases

sol = Solution()

assert sol.maximumCandies([5, 8, 6], 3) == 5  # provided example 1
assert sol.maximumCandies([2, 5], 11) == 0  # provided example 2

assert sol.maximumCandies([1], 1) == 1  # single pile, exact fit
assert sol.maximumCandies([10], 3) == 3  # single pile split into parts
assert sol.maximumCandies([10], 20) == 0  # impossible distribution

assert sol.maximumCandies([4, 4, 4], 3) == 4  # equal piles
assert sol.maximumCandies([4, 4, 4], 6) == 2  # splitting required
assert sol.maximumCandies([4, 4, 4], 12) == 1  # every candy used
assert sol.maximumCandies([4, 4, 4], 13) == 0  # insufficient total candies

assert sol.maximumCandies([10000000], 1) == 10000000  # maximum pile size
assert sol.maximumCandies([10000000], 1000000000000) == 0  # huge k

assert sol.maximumCandies([1, 2, 3, 4, 5], 5) == 2  # mixed pile sizes
assert sol.maximumCandies([9, 7, 5], 4) == 4  # optimal in middle range
assert sol.maximumCandies([100, 200, 300], 10) == 50  # multiple splits
Test Why
[5,8,6], k=3 Validates the first provided example
[2,5], k=11 Validates impossible allocation
[1], k=1 Smallest valid input
[10], k=3 Single pile split among children
[10], k=20 More children than candies
[4,4,4], k=3 Equal-sized piles
[4,4,4], k=6 Requires splitting
[4,4,4], k=12 Every candy distributed individually
[4,4,4], k=13 Total candies insufficient
[10000000], k=1 Maximum pile constraint
[10000000], k=10^12 Stress test for huge k
[1,2,3,4,5], k=5 Mixed pile sizes
[9,7,5], k=4 Binary search boundary behavior
[100,200,300], k=10 Multiple piles contributing

Edge Cases

One important edge case occurs when the total number of candies is less than k. In this scenario, even giving one candy per child is impossible. A naive implementation might accidentally return 1 if it does not carefully verify feasibility. The binary search handles this naturally because even mid = 1 fails the feasibility check, leaving the answer as 0.

Another tricky case involves a single pile. Since piles cannot be merged, all children must receive candies from subdivisions of the same pile. For example, candies = [10] and k = 3 should return 3, not 10 // 3 = 3.33 or 4. The implementation correctly uses integer division to count only complete groups.

A third important edge case is extremely large values of k, up to 10^12. Any algorithm attempting to simulate children individually would fail due to time complexity. The binary search solution avoids dependence on k entirely and only performs arithmetic operations on pile sizes.

Finally, boundary values around feasibility can easily introduce off-by-one errors. For example, when mid is feasible, we must continue searching to the right because a larger answer may still exist. At the same time, we preserve the current feasible value in answer. This ensures the algorithm returns the maximum valid candy count rather than merely any valid count.