LeetCode 2226: Maximum Candies Allocated to K Children

Explanation

To solve this problem, we need to find the maximum number of candies each child can get when dividing the candies among k children. We can iterate through the array to find the maximum number of candies in a single pile. Then, we can use binary search to find the maximum number of candies each child can get, starting from 1 to the maximum number of candies in a single pile. We can use a helper function to check if it is possible to distribute candies among k children with the given maximum candies.

Algorithm:

1. Find the maximum number of candies in a single pile.
2. Perform binary search to find the maximum number of candies each child can get.
3. Use a helper function to check if it is possible to distribute candies among k children with the given maximum candies.
4. Update the result accordingly.

Time Complexity: O(n log m), where n is the number of piles of candies and m is the maximum number of candies in a single pile. Space Complexity: O(1)

class Solution {
    public int maxCandies(int[] candies, int k) {
        int maxCandies = 0;
        for (int candy : candies) {
            maxCandies = Math.max(maxCandies, candy);
        }
        
        int left = 1, right = maxCandies;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canDistribute(candies, k, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private boolean canDistribute(int[] candies, int k, int maxCandies) {
        int count = 0;
        for (int candy : candies) {
            count += candy / maxCandies;
        }
        return count >= k;
    }
}