Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2226.html
2226. Maximum Candies Allocated to K Children (Medium)
You are given a 0indexed 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 <= 10^{5}
1 <= candies[i] <= 10^{7}
1 <= k <= 10^{12}
Companies:
Google
Related Topics:
Array, Binary Search
Similar Questions:
 Koko Eating Bananas (Medium)
 Minimum Limit of Balls in a Bag (Medium)
 Minimum Speed to Arrive on Time (Medium)
 Maximum Number of Removable Characters (Medium)
 Minimized Maximum of Products Distributed to Any Store (Medium)
 Minimum Time to Complete Trips (Medium)
Solution 1. Binary Answer
Binary search in range L = 1, R = max(A)
.
For a given M = (L + R) / 2
, we test if we can give M
candies to each child, which can be done by traversing the array once, taking O(N)
time.
If possible/valid, we make L = M + 1
; otherwise, we make R = M  1
.
In the end, since we are looking for the greatest valid number, we return R
.

// OJ: https://leetcode.com/problems/maximumcandiesallocatedtokchildren/ // Time: O(Nlog(sum(A))) // Space: O(1) class Solution { public: int maximumCandies(vector<int>& A, long long k) { long L = 1, R = *max_element(begin(A), end(A)), N = A.size(); auto valid = [&](long m) { long cnt = 0; for (int n : A) { cnt += n / m; if (cnt >= k) return true; } return false; }; while (L <= R) { long M = L + (R  L) / 2; if (valid(M)) L = M + 1; else R = M  1; } return R; } };

class Solution: def maximumCandies(self, candies: List[int], k: int) > int: left, right = 0, max(candies) while left < right: mid = (left + right + 1) >> 1 cnt = sum(v // mid for v in candies) if cnt >= k: left = mid else: right = mid  1 return left ############ # 2226. Maximum Candies Allocated to K Children # https://leetcode.com/problems/maximumcandiesallocatedtokchildren/ class Solution: def maximumCandies(self, candies: List[int], k: int) > int: n = len(candies) total = sum(candies) if total < k: return 0 def good(b): count = 0 for x in candies: count += x // b return count >= k left, right = 1, 10 ** 18 while left < right: mid = left + (right  left + 1) // 2 if good(mid): left = mid else: right = mid  1 return left

class Solution { public int maximumCandies(int[] candies, long k) { int left = 0, right = (int) 1e7; while (left < right) { int mid = (left + right + 1) >> 1; long cnt = 0; for (int v : candies) { cnt += v / mid; } if (cnt >= k) { left = mid; } else { right = mid  1; } } return left; } }

func maximumCandies(candies []int, k int64) int { left, right := 0, int(1e7) for left < right { mid := (left + right + 1) >> 1 var cnt int64 for _, v := range candies { cnt += int64(v / mid) } if cnt >= k { left = mid } else { right = mid  1 } } return left }
Discuss
https://leetcode.com/problems/maximumcandiesallocatedtokchildren/discuss/1908820