Maximum Candies Allocated to K Children

Medium
824.

Maximum Candies Allocated to K Children

Maximum Candies Allocated to K Children is a medium coding problem on arrays and binary search, asked in Amazon, Google and CRED interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} candies
 * @param {number} k
 * @return {number}
 */
var maximumCandies = function(candies, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Candies Allocated to K Children — Problem & Solution

Maximum Candies Allocated to K Children solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Candies Allocated to K Children is a medium coding problem on arrays and binary search, asked in Amazon, Google and CRED interviews.

  • 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

Hints for Maximum Candies Allocated to K Children

  1. Hint 1

    If each child can get c candies, they can also get any smaller amount — the feasibility is monotone.

  2. Hint 2

    For a candidate c, pile i yields floor(candies[i] / c) children's worth.

  3. Hint 3

    Binary search the largest c whose total reaches k.

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

Java

private static boolean canAllocate(int[] candies, int k, int size) {
    long cnt = 0;
    for (int c : candies) {
        cnt += c / size;
        if (cnt >= k) return true;
    }
    return cnt >= k;
}

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

C++

static bool canAllocate(vector<int>& candies, int k, int size) {
    long long cnt = 0;
    for (int c : candies) {
        cnt += c / size;
        if (cnt >= k) return true;
    }
    return cnt >= k;
}

int maximumCandies(vector<int>& candies, int k) {
    int hi = 0;
    for (int c : candies) hi = max(hi, c);
    int lo = 1, ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canAllocate(candies, k, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search