2226.Maximum_Candies_Allocated_to_K_Children(Medium).md

2226. Maximum Candies Allocated to K Children (Medium)

Date and Time: Mar 13, 2025, 23:15 (EST)

Link: https://leetcode.com/problems/maximum-candies-allocated-to-k-children

Question:

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.

Hint 1: For a fixed number of candies c, how can you check if each child can get c candies?

Hint 2: Use binary search to find the maximum c as the answer.

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}$

Walk-through:

We can run binary search on range [1, max(candies)] to find the candies m and for each pile i in candies, we calculate tmp += i // m, and check if tmp >= k, then we can update ans = tmp. Next, update l, r accordingly.

Python Solution:

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        # Run Binary Search on the range [1, max(candies)], pick candies c from here
        # For each candy // m to see if total pile can be divided by m candies for k children. Update l, r accordingly

        # TC: O(nlog(m)), n=len(candies), m=max(candies), SC: O(1)
        l, r = 1, max(candies)      # [1, max(candies)]
        ans = 0
        while l <= r:
            m = (l+r) // 2
            tmp = 0
            # Calculate how many children get m candies
            for i in candies:
                tmp += i // m
            # If not enough for k children, look for greater m
            if tmp >= k:
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans

Time Complexity: $O(nlog(m))$, we run binary search and iterate candies everytime.
Space Complexity: $O(1)$