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.
For example:
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.
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.
Could you provide an efficient algorithm to solve this problem?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The goal is to find the largest amount of candy we can give to each child such that we can give candy to all the children. The brute force strategy involves trying every possible candy amount, from very small to very large, to see if we can distribute the candies that way.
Here's how the algorithm would work step-by-step:
def maximum_candies(candies_piles, number_of_children):
max_candies_possible = 0
# Iterate through possible candy amounts, starting from 1.
for current_candy_amount in range(1, sum(candies_piles) + 1):
candies_distributed = 0
for pile in candies_piles:
candies_distributed += pile // current_candy_amount
# Check if we can distribute the current amount to all children.
if candies_distributed >= number_of_children:
max_candies_possible = current_candy_amount
# If we can't distribute enough, the previous amount was the maximum
else:
break
return max_candies_possible
The key is to avoid checking every possible candy distribution. Instead, we can use a clever technique to quickly narrow down the possibilities, focusing on finding the largest possible number of candies we can give to each child while still giving to all the children.
Here's how the algorithm would work step-by-step:
def maximum_candies_allocated_to_k_children(candies, number_of_children):
left_bound = 0
right_bound = max(candies)
while left_bound <= right_bound:
max_candies_per_child = (left_bound + right_bound) // 2
# Avoid division by zero.
if max_candies_per_child == 0:
if number_of_children > 0:
return 0
else:
return max(candies)
number_of_children_given_candies = 0
for pile_of_candies in candies:
number_of_children_given_candies += pile_of_candies // max_candies_per_child
# Check if enough children can receive candies.
if number_of_children_given_candies >= number_of_children:
# Increase the lower bound, since we can give more candies.
left_bound = max_candies_per_child + 1
else:
# Decrease the upper bound, since the amount is too high.
right_bound = max_candies_per_child - 1
# Return the maximum candies that can be given to each child.
return right_bound
Case | How to Handle |
---|---|
candies array is null or empty | Return 0 since no candies can be allocated to any children. |
k is 0 | Return 0 since no children need candies. |
candies array contains a zero | The binary search will still function correctly, with 0 as a valid allocation size. |
candies array contains very large numbers that could lead to integer overflow when dividing | Use long data type to prevent integer overflow during calculations. |
The candies array contains only 1 value | Return the candies[0] / k. |
The sum of all candies is less than k | The maximum possible candy allocation per child is 0. |
k is extremely large, much larger than the number of candies. | The result of the division will likely be small, but the binary search still works. |
Maximum sized input array and k, close to integer limits. | Ensure algorithm is O(n log m) where n is number of piles and m is maximum value of a pile, and avoid unnecessary memory allocation. |