Get started

Maximum Candies Allocated to K Children — Medium Problem & Solution

Pile i holds candies[i] candies. You may split a pile into any number of sub-piles, but you may not merge piles.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, Cred
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Pile i holds candies[i] candies. You may split a pile into any number of sub-piles, but you may not merge piles.

Every one of the k children must get the same number of candies, all from a single pile (leftovers may be discarded). Return the maximum number each child can get, or 0 if it is impossible.

Example 1

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: Two children take 5 from the 8-pile and the 6-pile; one takes the whole 5-pile.

Example 2

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are not enough candies for 11 children to get even one each.

Example 3

Input: candies = [4,7,5], k = 4
Output: 3

Constraints

  • 1 <= candies.length <= 100000
  • 1 <= candies[i] <= 10000000
  • 1 <= k <= 1000000000

How to solve Maximum Candies Allocated to K Children

Binary search the per-child amount. For a candidate c, each pile independently supplies floor(candies[i] / c) shares, and the shares cannot be combined across piles — which is exactly what the floor captures.

Approach

  1. Search c over [1, max(candies)].
  2. can(c): sum floor(candies[i] / c) and stop early once it reaches k.
  3. Keep the largest feasible c; if none is, the answer is 0.

Why it works

Raising c weakly lowers every pile's share count, so the total is non-increasing and the feasible amounts form a prefix. The floor is correct because a child's candies must come from one pile — a remainder smaller than c is simply wasted, it cannot be topped up from elsewhere.

Complexity

  • Time — O(n log M) where M is the largest pile
  • Space — O(1)

Pitfalls

  • The share count reaches 10^5 · 10^7 = 10^12, so it needs 64-bit or an early exit once k is reached.
  • Answering 0 is legitimate and must be reachable — starting the search at 1 with a separate ans variable handles it.
  • Piles cannot be merged, so summing all candies and dividing by k is wrong.

Reference solution

Python

from typing import List

def maximumCandies(candies: List[int], k: int) -> int:
    def can(size: int) -> bool:
        cnt = 0
        for c in candies:
            cnt += c // size
            if cnt >= k:
                return True
        return cnt >= k

    lo, hi, ans = 1, max(candies), 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if can(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

JavaScript

var maximumCandies = function(candies, k) {
    var hi = 0, i;
    for (i = 0; i < candies.length; i++) if (candies[i] > hi) hi = candies[i];
    var can = function(size) {
        var cnt = 0;
        for (var j = 0; j < candies.length; j++) {
            cnt += Math.floor(candies[j] / size);
            if (cnt >= k) return true;
        }
        return cnt >= k;
    };
    var lo = 1, ans = 0;
    while (lo <= hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (can(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1;
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue