Maximum Candies Allocated to K Children solution and explanation
Google
9 more videos on this problem
Maximum Candies Allocated to K Children - Leetcode 2226 - PythonNeetCodeIO · 19:24 · 11K views
Maximum Candies Allocated to K Children | Brute Force | Optimal | Leetcode 2226 | codestorywithMIKcodestorywithMIK · 27:44 · 9K views
Maximum Candies Allocated to K Children | Leetcode 2226Techdose · 19:44 · 4K views
2226. Maximum Candies Allocated to K Children || Leetcode Weekly Contest 287 || Leetcode 2226Bro Coders · 13:30 · 4K views
Maximum Candies Allocated to K Children | Leetcode 2226 |Range Based Binary Search | Contest 287 🔥🔥Coding Decoded · 11:20 · 3K views
2226. Maximum Candies Allocated to K Children | Binary Search 2nd TemplateAryan Mittal · 19:53 · 1K views
LeetCode 2226 Maximum Candies Allocated to K Children | Binary Search on Answers | Google MetaCode Harmony · 19:07 · 340 views
Leetcode Weekly 287 | 5219. Maximum Candies Allocated to K ChildrencodingMohan · 10:41 · 271 views
LEETCODE 2226 Maximum Candies Allocated to K Children(Medium)Chan_Rox_ · 9:30 · 140 views
2226. Maximum Candies Allocated to K Children | Leetcode Daily - PythonLeetcode Daily · 4:09 · 57 views
The problem
You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.
You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.
Return the maximum number of candies each child can get.
Example 1:
Input: candies = [5,8,6], k = 3 Output: 5 Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.
Example 2:
Input: candies = [2,5], k = 11 Output: 0 Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.
Constraints:
1 <= candies.length <= 1051 <= candies[i] <= 1071 <= k <= 1012
Approach overview
Problem Overview: You receive an array candies where each element represents a pile of candies. You can split a pile into smaller piles but cannot combine piles. The goal is to distribute candies to k children so every child receives the same number of candies. Return the maximum candies each child can get.
Approach 1: Brute Force Enumeration (Time: O(n * M), Space: O(1))
A direct approach is to try every possible number of candies per child from 1 up to the largest pile size M. For each candidate value x, iterate through the array and compute how many children can be served using pile // x. If the total count is at least k, the distribution works. Track the largest valid x. This approach performs a full array scan for every possible candy count, which becomes too slow when the maximum pile value is large.
Approach 2: Binary Search on Answer (Time: O(n log M), Space: O(1))
The key observation: if you can give x candies per child, then any value smaller than x is also feasible. This monotonic property makes the problem ideal for binary search. Instead of testing every possible value, search the range [1, max(candies)]. For each midpoint mid, iterate through the array and compute how many children can be served using pile // mid. If the total number of children served is at least k, increase the lower bound to search for a larger answer. Otherwise reduce the upper bound.
The counting step is straightforward: loop through the array and accumulate pile // mid. This represents how many equal portions of size mid each pile can contribute. The algorithm repeatedly narrows the search space until the largest feasible value is found.
This method avoids scanning every possible candy amount. Instead, it performs roughly log(max(candies)) checks, each requiring a single pass through the array. With large pile sizes (up to millions or billions), this improvement is substantial.
Recommended for interviews: Binary search on the answer is the expected solution. Interviewers look for recognition of the monotonic feasibility condition and the ability to convert the problem into a search space over possible answers. Mentioning the brute force approach first shows understanding of the constraint, while the binary search optimization demonstrates strong algorithmic reasoning.
Approach 1: Binary Search Approach
The binary search approach involves searching for the maximum number of candies each child can get. We perform a binary search on the possible number of candies from 0 up to the largest pile of candies. For each candidate number of candies in our search, we check if it is feasible to allocate that number of candies to each of the k children. This feasibility check is done by attempting to distribute the candies such that each child receives the desired number.
By checking the feasibility at each step, we narrow down our search to the largest feasible number of candies per child.
def can_distribute(candies, k, min_candies):
count = 0
for candy in candies:
count += candy // min_candies
if count >= k:
return True
return False
def max_candies(candies, k):
low, high = 0, 10**7
result = 0
while low <= high:
mid = (low + high) // 2
if can_distribute(candies, k, mid):
result = mid
low = mid + 1
else:
high = mid - 1
return result
candies = [5, 8, 6]
k = 3
print(f"Maximum candies per child: {max_candies(candies, k)}")import java.util.*;
public class MaxCandies {
public static boolean canDistribute(int[] candies, long k, int minCandies) {
long count = 0;
for (int candy : candies) {
count += candy / minCandies;
if (count >= k) return true;
}
return false;
}
public static int maxCandies(int[] candies, long k) {
int low = 0, high = (int)1e7;
int result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canDistribute(candies, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] candies = {5, 8, 6};
long k = 3;
System.out.println("Maximum candies per child: " + maxCandies(candies, k));
}
}#include <iostream>
#include <vector>
using namespace std;
bool canDistribute(const vector<int>& candies, int k, int minCandies) {
long long count = 0;
for(auto candy : candies) {
count += candy / minCandies;
if(count >= k) return true;
}
return false;
}
int maxCandies(vector<int>& candies, int k) {
int low = 0, high = 1e7;
int result = 0;
while(low <= high) {
int mid = low + (high - low) / 2;
if(canDistribute(candies, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
int main() {
vector<int> candies = {5, 8, 6};
int k = 3;
cout << "Maximum candies per child: " << maxCandies(candies, k) << endl;
return 0;
}function canDistribute(candies, k, minCandies) {
let count = 0;
for (const candy of candies) {
count += Math.floor(candy / minCandies);
if (count >= k) return true;
}
return false;
}
function maxCandies(candies, k) {
let low = 0, high = 10 ** 7;
let result = 0;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (canDistribute(candies, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
const candies = [5, 8, 6];
const k = 3;
console.log(`Maximum candies per child: ${maxCandies(candies, k)}`);#include <stdio.h>
int canDistribute(int* candies, int candiesSize, long long k, int minCandies) {
long long count = 0;
for(int i = 0; i < candiesSize; i++) {
count += candies[i] / minCandies;
if (count >= k) {
return 1;
}
}
return 0;
}
int maxCandies(int* candies, int candiesSize, long long k) {
int low = 0, high = 1e7;
int result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canDistribute(candies, candiesSize, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
int main() {
int candies[] = {5, 8, 6};
int k = 3;
int size = sizeof(candies) / sizeof(candies[0]);
int result = maxCandies(candies, size, k);
printf("Maximum candies per child: %d\n", result);
return 0;
}using System;
class MaximumCandies {
static bool CanDistribute(int[] candies, long k, int minCandies) {
long count = 0;
foreach (var candy in candies) {
count += candy / minCandies;
if (count >= k) return true;
}
return false;
}
static int MaxCandies(int[] candies, long k) {
int low = 0, high = 10000000;
int result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (CanDistribute(candies, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
static void Main() {
int[] candies = { 5, 8, 6 };
long k = 3;
Console.WriteLine("Maximum candies per child: " + MaxCandies(candies, k));
}
}In the Python solution, can_distribute checks if it is feasible for all children to receive the specified number of candies using integer division. The function max_candies carries out a binary search, adjusting the search bounds based on the feasibility results to determine the largest feasible number of candies per child.
Time Complexity: O(n * log(m)), where n is number of piles and m is the maximum candies in a pile.
Space Complexity: O(1), due to non-usage of extra space.
Approach 2: Binary Search
We notice that if each child can receive v candies, then for any v' \lt v, each child can also receive v' candies. Therefore, we can use binary search to find the maximum v such that each child can receive v candies.
We define the left boundary of the binary search as l = 0 and the right boundary as r = max(candies), where max(candies) represents the maximum value in the array candies. During the binary search, we take the middle value v = \left\lfloor \frac{l + r + 1}{2} \right\rfloor each time, and then calculate the total number of candies each child can receive. If the total is greater than or equal to k, it means each child can receive v candies, so we update the left boundary l = v. Otherwise, we update the right boundary r = v - 1. Finally, when l = r, we have found the maximum v.
The time complexity is O(n times log M), where n is the length of the array candies, and M is the maximum value in the array candies. The space complexity is O(1).
function maximumCandies(candies: number[], k: number): number {
let [l, r] = [0, Math.max(...candies)];
while (l < r) {
const mid = (l + r + 1) >> 1;
const cnt = candies.reduce((acc, cur) => acc + Math.floor(cur / mid), 0);
if (cnt >= k) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func maximumCandies(candies []int, k int64) int {
return sort.Search(1e7, func(v int) bool {
v++
var cnt int64
for _, x := range candies {
cnt += int64(x / v)
}
return cnt < k
})
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(n * log(m)), where n is number of piles and m is the maximum candies in a pile. |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * M) | O(1) | Conceptual baseline or when maximum pile size is very small |
| Binary Search on Answer | O(n log M) | O(1) | Optimal solution for large arrays and large pile values |
Frequently asked questions
Is Maximum Candies Allocated to K Children easy or hard?
Maximum Candies Allocated to K Children is rated Medium difficulty. The implementation is simple once you recognize the binary search on answer pattern, but identifying the monotonic feasibility condition can be tricky for beginners.
Maximum Candies Allocated to K Children Python/Java solution
The standard implementation performs binary search between 1 and max(candies). For each midpoint, iterate through the array and accumulate pile // mid to count served children. This logic translates directly across Python, Java, C++, C#, and JavaScript with identical O(n log M) complexity.
How to solve Maximum Candies Allocated to K Children in O(n log M)?
Use binary search over the possible candies per child. Set the search range from 1 to the maximum pile size. For each midpoint value, iterate through the piles and compute how many children can be served using pile // mid. If the total is at least k, move the search to the right to try a larger value; otherwise move left.
What is the best approach for Maximum Candies Allocated to K Children?
Binary search on the answer is the most efficient approach. The idea is to search the maximum candies each child can receive in the range [1, max(candies)]. For each candidate value, iterate through the piles and count how many children can be served using integer division. This solution runs in O(n log M) time and O(1) space.
Is Maximum Candies Allocated to K Children asked at Google/Amazon/Meta?
Binary search on answer problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving resource allocation, maximizing minimum values, or splitting piles are common patterns used to test binary search reasoning and feasibility checks.
What data structure is used in Maximum Candies Allocated to K Children?
The main data structure is a simple array representing candy piles. The algorithm relies on binary search over the answer space and a linear scan of the array to compute how many children can be served for a given candidate value.
What is the time complexity of Maximum Candies Allocated to K Children?
The optimal solution runs in O(n log M) time, where n is the number of piles and M is the maximum number of candies in a pile. Each binary search step scans the array once to count how many children can receive the candidate amount. Space complexity remains O(1) since only counters and pointers are used.