Problem 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.
Key Insights
- Each pile can be divided into any number of sub piles.
- The goal is to maximize the number of candies each child receives.
- Since k can be very large (up to 10^12), a binary search approach is suitable to efficiently find the maximum possible candies per child.
- The sum of candies from all piles must be divisible among the k children in a way that each child receives the same number.
Space and Time Complexity
Time Complexity: O(n log(max(candies)))
Space Complexity: O(1)
Solution
To solve the problem, we will use a binary search approach. The idea is to search for the maximum number of candies that can be allocated to each child. We will define our search range from 1 to the maximum number of candies in the piles. For each mid-point in our binary search, we will calculate how many children can be served if each child receives mid candies. If we can serve at least k children, we increase our search range to find a potentially larger number. Otherwise, we decrease our search range.