2226. Maximum Candies Allocated to K Children LeetCode Solution
In this guide, you will get 2226. Maximum Candies Allocated to K Children LeetCode Solution with the best time and space complexity. The solution to Maximum Candies Allocated to K Children problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Candies Allocated to K Children
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 be allocated candies from only 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.
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.
Time Complexity: O(n\log(\Sigma |\texttt{candies[i]}|))
Space Complexity: O(1)
2226. Maximum Candies Allocated to K Children LeetCode Solution in C++
class Solution {
public:
int maximumCandies(vector<int>& candies, long long k) {
int l = 1;
int r = accumulate(candies.begin(), candies.end(), 0L) / k;
while (l < r) {
const int m = (l + r) / 2;
if (numChildren(candies, m) < k)
r = m;
else
l = m + 1;
}
return numChildren(candies, l) >= k ? l : l - 1;
}
private:
long numChildren(const vector<int>& candies, int m) {
return accumulate(candies.begin(), candies.end(), 0L,
[&](long subtotal, int c) { return subtotal + c / m; });
};
}; /* code provided by PROGIEZ */
2226. Maximum Candies Allocated to K Children LeetCode Solution in Java
class Solution {
public int maximumCandies(int[] candies, long k) {
int l = 1;
int r = (int) (Arrays.stream(candies).asLongStream().sum() / k);
while (l < r) {
final int m = (l + r) / 2;
if (numChildren(candies, m) < k)
r = m;
else
l = m + 1;
}
return numChildren(candies, l) >= k ? l : l - 1;
}
private long numChildren(int[] candies, int m) {
return Arrays.stream(candies).asLongStream().reduce(0L, (subtotal, c) -> subtotal + c / m);
}
} // code provided by PROGIEZ
2226. Maximum Candies Allocated to K Children LeetCode Solution in Python
class Solution:
def maximumCandies(self, candies: list[int], k: int) -> int:
l = 1
r = sum(candies) // k
def numChildren(m: int) -> bool:
return sum(c // m for c in candies)
while l < r:
m = (l + r) // 2
if numChildren(m) < k:
r = m
else:
l = m + 1
return l if numChildren(l) >= k else l - 1 # code by PROGIEZ
