Maximum Candies Allocated to K Children

medium array binary search

Problem

Given candy piles where piles[i] candies are stacked, you can split a pile into smaller (equal-sized) sub-piles but not merge them. Find the maximum number of candies each of k children can receive.

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

Output5

Split into piles of 5: 1 + 1 + 1 = 3 sub-piles → enough for 3 children.

candies (comma-separated)

def maximum_candies(candies, k):
    lo, hi = 1, max(candies)
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        piles = sum(c // mid for c in candies)
        if piles >= k:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

function maximumCandies(candies, k) {
  let lo = 1, hi = Math.max(...candies), ans = 0;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    let piles = 0;
    for (const c of candies) piles += Math.floor(c / mid);
    if (piles >= k) { ans = mid; lo = mid + 1; }
    else hi = mid - 1;
  }
  return ans;
}

class Solution {
    public int maximumCandies(int[] candies, long k) {
        int lo = 1, hi = 0, ans = 0;
        for (int c : candies) hi = Math.max(hi, c);
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            long piles = 0;
            for (int c : candies) piles += c / mid;
            if (piles >= k) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }
}

int maximumCandies(vector<int>& candies, long long k) {
    int lo = 1, hi = *max_element(candies.begin(), candies.end()), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        long long piles = 0;
        for (int c : candies) piles += c / mid;
        if (piles >= k) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return ans;
}

Explanation

We want the largest candy size c such that we can cut the piles into at least k equal sub-piles of that size. The clue is that bigger c always gives fewer sub-piles, so the feasibility is monotone and we can binary-search the answer c.

For a candidate size mid, a pile of c candies yields c // mid whole sub-piles (you cannot merge piles, and leftovers are wasted). Summing c // mid over all piles tells us how many children we can serve.

If that total is >= k, the size works, so we record it and try a bigger size (lo = mid + 1). If it falls short, the size is too big and we shrink (hi = mid - 1). The search range starts at [1, max(candies)].

Example: candies = [5, 8, 6], k = 3. At size 5: 5//5 + 8//5 + 6//5 = 1 + 1 + 1 = 3, which meets k=3. At size 6 the total drops to 2, too few. So the answer is 5.

Each feasibility check is one linear pass, and binary search only needs about log(max) checks, making this fast.

Time: O(n log max(candies)) Space: O(1)