Skip to content

2226. Maximum Candies Allocated to K Children

Medium

Description

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.

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 <= 105
  • 1 <= candies[i] <= 107
  • 1 <= k <= 1012

Solutions

Time complexity: \(O(n \times \log M)\)

Space complexity: \(O(1)\)

Notes

We notice that if each child can receive v candies, then for any v' < 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 \(mid = (l+r+1)//2 = ⌊(l+r+1)/2⌋\) 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 = mid\). Otherwise, we update the right boundary \(r = mid - 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)\).

Way 1:

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        def f(mid):                     #f - numChildren is a function of candies
            return sum((c//mid) for c in candies)

        l, r = 1, max(candies)
        ans = 0
        while l <=r:
            mid = (l + r ) // 2
            if f(mid)>=k:
                ans = mid
                l = mid +1
            else:
                r = mid -1
        return ans

Way 2:

Tip

  • Binary Search different than the regular one
  • Problem function is monotonically decresing and we are looking for maximum
class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        def f(mid):                    #f - numChildren is a function of candies
            return sum((c//mid) for c in candies)

        l, r = 0, max(candies)
        while l<r:
            mid = (l + r +1) >> 1      #see deviation here from regular binary search
            if f(mid) >= k:
                l = mid                #see deviation here from regular binary search
            else:
                r = mid - 1            #see deviation here from regular binary search
        return l