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 <= 1012The 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.
The C solution uses a helper function canDistribute to verify the feasibility of distributing a certain number of candies to each child. We perform a binary search where the middle candy count is checked. If feasible, the result is updated to the mid-value and the search continues on the higher half. If not feasible, the search continues on the lower half. This process continues until the entire search space is exhausted. The final result will be the maximum number of candies each child can receive.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * log(m)), where n is the number of piles and m is the max candies available in any pile.
Space Complexity: O(1), as no additional space is used proportional to input size.
Maximum Candies Allocated to K Children - Leetcode 2226 - Python • NeetCodeIO • 9,000 views views
Watch 9 more video solutions →Practice Maximum Candies Allocated to K Children with our built-in code editor and test cases.
Practice on FleetCode