Problem Description

You are given an array candies where candies[i] represents the number of candies in the i-th pile. You are also given an integer k representing the number of children.

Your task is to distribute the candies among k children such that:

• Each child gets the same number of candies.
• Each child receives candies from only one pile (you can split a pile, but cannot combine piles).
• Your goal is to maximize the number of candies each child receives.
• If it's not possible to distribute candies to all k children, return 0.

In other words, you want to find the maximum integer x such that you can allocate x candies to each of k children, by splitting the piles as needed, but not combining them.

Constraints:

• 1 <= candies.length <= 10^5
• 1 <= candies[i] <= 10^7
• 1 <= k <= 10^12

Thought Process

At first glance, you might think to try every possible number of candies per child, from the maximum pile size down to 1, and check if it's possible to allocate that many candies to each child. However, with constraints as large as 10^12 for k, and piles up to 10^5, this naive approach would be far too slow.

Instead, it's important to realize that this is an optimization problem: for a given number of candies per child, we can check whether it's possible to satisfy all k children. If so, maybe we can do even better; if not, we need to try less. This pattern is perfect for binary search.

The key insight is to use binary search on the answer, i.e., the maximum number of candies per child, and efficiently check for each candidate value whether it's possible to allocate that many candies to all k children.

Solution Approach

Let's break down the steps for an efficient solution:

1. Binary Search on the Answer:
   • We know the answer must be between 1 and the largest pile size (since no child can get more candies than the largest pile).
   • We perform binary search over this range to find the largest possible number of candies per child.
2. Feasibility Check for Each Candidate:
   • For a given candidate number x, we need to check if we can give x candies to each of k children.
   • For each pile, we can make pile // x children happy from that pile (since we can split but not combine piles).
   • Sum this over all piles, and if the total is at least k, then x is feasible.
3. Iterative Search:
   • If x is feasible, try a higher value (move the lower bound up).
   • If not, try a lower value (move the upper bound down).
4. Return the Best Value:
   • Keep track of the best feasible value found during the search, and return it at the end.

This approach is efficient because it reduces the search space logarithmically and checks feasibility in linear time per iteration.

Example Walkthrough

Let's take an example:
candies = [5, 8, 6], k = 3

1. Set Search Range: The maximum possible candies per child is 8 (the largest pile).
2. Binary Search Iterations:
   • Try mid = (1 + 8) // 2 = 4
   • From 5: 5//4 = 1, from 8: 8//4 = 2, from 6: 6//4 = 1. Total = 1+2+1=4 ≥ 3. Feasible, try higher.
   • Try mid = (5 + 8) // 2 = 6
   • From 5: 5//6 = 0, from 8: 8//6 = 1, from 6: 6//6 = 1. Total = 0+1+1=2 < 3. Not feasible, try lower.
   • Try mid = (5 + 5) // 2 = 5
   • From 5: 5//5 = 1, from 8: 8//5 = 1, from 6: 6//5 = 1. Total = 1+1+1=3 ≥ 3. Feasible, try higher.
   • Try mid = (6 + 5) // 2 = 5 (already checked; binary search ends).
3. Result: The maximum candies per child is 5.

Time and Space Complexity

• Brute-force:
  • For each possible value from max(candies) down to 1, check feasibility.
  • Time complexity: O(max(candies) * n), which is too slow for large inputs.
  • Space complexity: O(1) extra space.
• Optimized (Binary Search):
  • Binary search over the range [1, max(candies)], which is at most 10⁷ steps (since candies[i] ≤ 10⁷).
  • Each step, we scan all n piles: O(n) per check.
  • Total time: O(n * log(max(candies))).
  • Space complexity: O(1) extra space (not counting input).

Summary

The problem asks us to maximize the number of candies each child gets, given the ability to split piles but not combine them. The key insight is to use binary search on the answer, checking for each candidate value if it's feasible to satisfy all children. This results in a highly efficient solution that works even for large inputs, thanks to the logarithmic reduction in search space and linear-time feasibility checks.

The solution is elegant because it transforms an apparently complex allocation problem into a straightforward search, leveraging efficient algorithms to deliver the answer.

Code Implementation

class Solution:
    def maximumCandies(self, candies, k):
        left, right = 1, max(candies)
        answer = 0

        def can_allocate(x):
            count = 0
            for pile in candies:
                count += pile // x
            return count >= k

        while left <= right:
            mid = (left + right) // 2
            if can_allocate(mid):
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        return answer
      

class Solution {
public:
    long long maximumCandies(vector<int>& candies, long long k) {
        long long left = 1, right = *max_element(candies.begin(), candies.end());
        long long answer = 0;

        auto can_allocate = [&](long long x) {
            long long count = 0;
            for (int pile : candies) {
                count += pile / x;
                if (count >= k) return true;
            }
            return count >= k;
        };

        while (left <= right) {
            long long mid = left + (right - left) / 2;
            if (can_allocate(mid)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }
};
      

class Solution {
    public int maximumCandies(int[] candies, long k) {
        int left = 1, right = 0;
        for (int pile : candies) {
            right = Math.max(right, pile);
        }
        int answer = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            long count = 0;
            for (int pile : candies) {
                count += pile / mid;
            }
            if (count >= k) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return answer;
    }
}
      

var maximumCandies = function(candies, k) {
    let left = 1, right = Math.max(...candies);
    let answer = 0;

    function canAllocate(x) {
        let count = 0;
        for (let pile of candies) {
            count += Math.floor(pile / x);
        }
        return count >= k;
    }

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (canAllocate(mid)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return answer;
};