Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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

Solution

Method 1 - Using Binary Search

The problem involves distributing piles of candies to k children such that each child receives the same number of candies from a single pile. Since we can split the piles but cannot merge them, the objective is to find the maximum number x such that at least k piles of size x can be created. To solve this efficiently:

Approach

  1. Binary Search:

    • Use binary search to determine the maximum possible number x of candies each child can receive.
    • Searching is performed in the range from 1 to max(candies), where max(candies) is the largest pile size.
    • For each candidate x, check if it is possible (feasible) to distribute the candies such that at least k children receive a pile of size x or larger.

  2. Feasibility Check:

    • For a given candidate x, calculate how many children can be served. This is done by summing up pile // x for all piles in the candies array.
    • If the total number of children served is greater than or equal to k, then x is feasible.

  3. Binary Search Adjustment:

    • If x is feasible, search for a larger x (right side of the binary search range).
    • Otherwise, search for a smaller x (left side of the binary search range).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public int maximumCandies(int[] candies, long k) {
        // If the total candies in all piles are not enough for k children, return 0.
        long totalCandies = 0;
        for (int c : candies) {
            totalCandies += c;
        }
        if (totalCandies < k) return 0;

        int low = 1, high = Integer.MAX_VALUE, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2; // Calculate mid-point
            if (canDistribute(candies, k, mid)) {
                ans = mid; // If feasible, update ans and move to the larger range
                low = mid + 1;
            } else {
                high = mid - 1; // Otherwise, move to the smaller range
            }
        }
        return ans;
    }

    private boolean canDistribute(int[] candies, long k, int x) {
        long count = 0; // Count of children who can get at least x candies
        for (int c : candies) {
            count += c / x; // Calculate number of children that can be served from each pile
            if (count >= k) return true; // Stop early if we can serve k children
        }
        return false; // Cannot serve k children with current x
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        def can_distribute(x: int) -> bool:
            # Check if it is possible to distribute 'x' candies to at least 'k' children
            count = sum(c // x for c in candies)
            return count >= k

        total_candies = sum(candies)
        if total_candies < k:
            return 0  # Not enough candies for 'k' children

        low, high, ans = 1, max(candies), 0
        while low <= high:
            mid = (low + high) // 2  # Middle value in binary search
            if can_distribute(mid):  # Check feasibility of current 'mid'
                ans = mid  # Update result if feasible
                low = mid + 1  # Look for larger values
            else:
                high = mid - 1  # Look for smaller values

        return ans  # Maximum candies each child can receive

Complexity

  • ⏰ Time complexity: O(n*log(M)), where n is the size of array and M is the max number of candles.
    • Binary search operates over the range [1, max(candies)] with around log(max(candies)) iterations.
    • For each iteration, the feasibility check scans the candies array (size n) in O(n) time.
    • Total time complexity is O(n * log(max(candies))).
  • 🧺 Space complexity: O(1)