2226. Maximum Candies Allocated to K Children
Problem Description
In this problem, you have an array candies
, where each element represents a pile of candies (with index starting from 0). Each pile contains a certain number of candies denoted by candies[i]
. The array gives you the flexibility to split any pile into smaller sub-piles but does not allow you to combine two different piles into one.
Additionally, you are given an integer k
, which represents the number of children to whom the candies must be distributed. The goal is to distribute the candies to k
children in such a way that each child receives exactly the same number of candies. However, each child can receive at most one pile (which can potentially be a sub-pile of one of the original piles), and it's possible that not all piles will be distributed.
The objective is to find the maximum number of candies that you can give to each child under these conditions.
Intuition
To solve this problem, we need to determine the maximum number of candies each child can get. The key here is understanding that if we can give x
candies to each child, then surely we can give any amount less than x
candies as well (by dividing the piles into smaller ones). However, we cannot always give more than x
candies. So, our solution will likely involve finding the optimal x
.
One way to approach this is through binary search. The minimum number of candies a child could get is 0
(if k
is larger than the total number of candies available) and the maximum is the size of the largest pile in candies
.
Using binary search, we can find the largest possible value for x
in the range [0, max(candies)]
such that we can still distribute the candies to k
children with each child receiving x
candies. We consider a middle value mid
within this range and check if it is possible to divide the piles in such a way that at least k
children can receive mid
candies each. If it is possible, then we know we can try to increase x
and search in the upper half of the range; otherwise, we search in the lower half of the range.
The provided code implements this binary search approach to efficiently determine the maximum amount of candies that can be distributed to each child such that every child receives the same amount.
Learn more about Binary Search patterns.
Solution Approach
The solution provided is a binary search approach, which solves the problem by iterating over a possible range of candies that can be distributed to each child and narrowing down that range to find an optimal solution.
Here's a step-by-step explanation of the implementation:
-
We initialize two pointers,
left
andright
.left
represents the lower bound (minimum number of candies we can give per child), set to 0, since it's possible that we cannot give any candies to the children if there are fewer candies thank
.right
represents the upper bound (maximum number of candies we can give to each child), which would be the largest pile incandies
, since no child can receive more than the size of the largest pile.1left, right = 0, max(candies)
-
We perform the binary search by checking the middle value between the
left
andright
pointers. This middle value,mid
, posits a hypothetical maximum number of candies to be distributed per child.1mid = (left + right + 1) >> 1
-
For the current middle value
mid
, we calculate whether it is possible to achieve this distribution by summing up the number of children we can satisfy if each were to be givenmid
candies. This is done by dividing each pile size bymid
and summing those values across all piles.1cnt = sum(v // mid for v in candies)
-
If
cnt
(the number of potential children receivingmid
candies) is greater than or equal tok
, then distributingmid
candies to each child is possible, and we can potentially give more, so we adjust theleft
pointer tomid
.1if cnt >= k: 2 left = mid
-
If
cnt
is less thank
, then we cannot give outmid
candies to each child, and we might need to reduce the number of candies we give to each child. Therefore, we adjust theright
pointer tomid - 1
.1else: 2 right = mid - 1
-
This search process continues until
left
andright
converge, which happens whenleft == right
. When the binary search terminates,left
will hold the maximum number of candies that we can distribute to each child. -
Finally, the function returns the value of
left
as the answer.1return left
The algorithm effectively uses binary search on a sorted range of possible candy distributions, utilizing the idea that if a certain amount x
is doable, so is any amount less than x
. We use division to check the feasibility of each mid
point, counting the number of children that can be satisfied with mid
candies and adjusting our search space accordingly until we find the maximum feasible distribution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example to illustrate the solution approach. Suppose we have an array of piles of candies given as candies = [4, 7, 12, 19]
, and the number of children k = 3
.
We want to distribute these candies such that each of the 3 children gets the same number of candies, and we are tasked with finding the maximum number of candies each child can get.
-
We begin by initializing
left = 0
andright = 19
(19 being the largest pile of candies). -
We perform binary search. Initially,
mid = (0 + 19 + 1) >> 1
is10
. We check if we can distribute 10 candies to each child. -
To check the feasibility, we sum up how many children can receive 10 candies:
- Pile 1 can be divided into
4 // 10
children, which is0
. - Pile 2 can be divided into
7 // 10
children, which is0
. - Pile 3 can be divided into
12 // 10
children, which is1
. - Pile 4 can be divided into
19 // 10
children, which is1
.
The total number of children who can receive candies is
0 + 0 + 1 + 1 = 2
. - Pile 1 can be divided into
-
Since we can only satisfy 2 children, but we need to satisfy 3,
10
candies per child is too high. So, we setright = mid - 1
, which is9
. -
We repeat the binary search. Now,
mid = (0 + 9 + 1) >> 1
is5
. We calculate:- Pile 1 can be divided into
4 // 5
children, which is0
. - Pile 2 can be divided into
7 // 5
children, which is1
. - Pile 3 can be divided into
12 // 5
children, which is2
. - Pile 4 can be divided into
19 // 5
children, which is3
.
Now, the total is
0 + 1 + 2 + 3 = 6
. - Pile 1 can be divided into
-
Since the total number of children who can receive candies is now 6, and we only need to satisfy 3, we have found that giving 5 candies per child is possible. We could potentially give more, so we adjust
left
tomid
, which is5
. -
We continue this process, but now as
left
andright
converge, both will be equal to5
, and the loop ends. -
The binary search concludes with
left = 5
, which is the maximum number of candies we can distribute to each child.
Each child can receive 5 candies, which can be distributed as follows:
- Child 1 receives 5 candies from pile 2.
- Child 2 receives 5 candies from pile 3.
- Child 3 receives 5 candies from pile 4.
2 candies will remain in pile 3, and 14 candies will remain in pile 4, but since we can't combine them and we can only give one pile to each child, this is the most we can distribute evenly.
Solution Implementation
1class Solution:
2 def maximumCandies(self, candies: List[int], k: int) -> int:
3 # Initialize left to 0 (minimum possible result) and
4 # right to the maximum number of candies in any pile
5 left, right = 0, max(candies)
6
7 # Binary search for the highest number of candies per child
8 while left < right:
9 # Mid is the number of candies to distribute per child; add 1 and
10 # shift right by 1 to get the upper middle for even numbers
11 mid = (left + right + 1) // 2
12
13 # Count how many children can receive 'mid' number of candies
14 count = sum(candy // mid for candy in candies)
15
16 # If the number of children that can receive 'mid' candies is at least k,
17 # mid can be a potential answer, so we move left pointer up to mid
18 if count >= k:
19 left = mid
20 # Otherwise, we decrease the right pointer, as we need less candies per child
21 else:
22 right = mid - 1
23
24 # left is now the maximum number of candies per child that we can distribute
25 return left
26
1class Solution {
2 public int maximumCandies(int[] candies, long k) {
3 // Initialize the search range for the maximum number of candies per child.
4 int low = 0;
5 int high = (int) 1e7;
6
7 // Use a binary search to find the maximum number of candies
8 // that can be distributed to `k` children evenly.
9 while (low < high) {
10 // Calculate the middle point of the current search range.
11 // Use `+ 1` to ensure the `mid` is biased towards the higher part of the range.
12 // The bitwise right shift operator `>> 1` effectively divides the sum of `low` and `high` by 2.
13 int mid = (low + high + 1) >> 1;
14
15 // Count the total number of children that can receive `mid` candies.
16 long count = 0;
17 for (int candy : candies) {
18 count += candy / mid;
19 }
20
21 // If the total number of children that can receive `mid` candies is at least `k`,
22 // then we know that it's possible to give out at least `mid` candies to each child.
23 // So we update `low` to `mid` to search in the higher half of the range next.
24 if (count >= k) {
25 low = mid;
26 }
27 // If not, we need to search in the lower half of the range, so we adjust `high`.
28 else {
29 high = mid - 1;
30 }
31 }
32
33 // `low` will represent the highest number of candies that can be distributed evenly to `k` children.
34 return low;
35 }
36}
37
1class Solution {
2public:
3 int maximumCandies(vector<int>& candies, long long totalChildren) {
4 // Initialize the search range
5 int minCandies = 0, maxCandies = 1e7;
6
7 // Perform a binary search to find the maximum number of candies
8 // that can be distributed to each child
9 while (minCandies < maxCandies) {
10 // Calculate the mid-point for the current search range
11 int mid = (minCandies + maxCandies + 1) >> 1;
12
13 // Counter to record the total number of children we can distribute
14 // candies to with the current 'mid' number of candies per child
15 long long childCount = 0;
16
17 // Iterate through each pile of candies
18 for (int candiesInPile : candies) {
19 // Increment the count by the number of children we can satisfy
20 // with the current pile using 'mid' candies per child
21 childCount += candiesInPile / mid;
22 }
23
24 // If we can give at least 'mid' candies to 'totalChildren' or more,
25 // adjust the lower bound of the search range
26 if (childCount >= totalChildren) {
27 minCandies = mid;
28 } else {
29 // Otherwise, reduce the upper bound of the search range
30 maxCandies = mid - 1;
31 }
32 }
33
34 // After narrowing down the search range, 'minCandies' will hold the
35 // maximum number of candies that can be distributed to each child
36 return minCandies;
37 }
38};
39
1// Function to calculate the maximum number of candies
2// that can be distributed to each child
3function maximumCandies(candies: number[], totalChildren: number): number {
4 // Initialize the search range
5 let minCandies: number = 0;
6 let maxCandies: number = 1e7;
7
8 // Perform a binary search to find the maximum number of candies
9 // that can be distributed to each child
10 while (minCandies < maxCandies) {
11 // Calculate the mid-point for the current search range
12 let mid: number = Math.floor((minCandies + maxCandies + 1) / 2);
13
14 // Counter to record the total number of children we can distribute
15 // candies to with the current 'mid' number of candies per child
16 let childCount: number = 0;
17
18 // Iterate through each pile of candies
19 for (let candiesInPile of candies) {
20 // Increment the count by the number of children we can satisfy
21 // with the current pile using 'mid' candies per child
22 childCount += Math.floor(candiesInPile / mid);
23 }
24
25 // If we can give at least 'mid' candies to 'totalChildren' or more,
26 // adjust the lower bound of the search range
27 if (childCount >= totalChildren) {
28 minCandies = mid;
29 } else {
30 // Otherwise, reduce the upper bound of the search range
31 maxCandies = mid - 1;
32 }
33 }
34
35 // After narrowing down the search range, 'minCandies' will hold the
36 // maximum number of candies that can be distributed to each child
37 return minCandies;
38}
39
Time and Space Complexity
Time Complexity
The time complexity of the given code is mainly determined by the while loop and the sum operation within that loop. The while
loop uses a binary search pattern which runs until left
is less than right
. In terms of the binary search, this takes O(log(max(candies)))
time, because we are repeatedly halving the search space that starts with the maximum value in candies
.
Inside this loop, there is a sum operation which includes a list comprehension that iterates over all elements in the candies
list. This operation has a time complexity of O(n)
where n
is the number of elements in candies
, because it must visit each element once.
Since the list comprehension is done every time the while loop runs, the combined time complexity is the product of the two, resulting in O(n * log(max(candies)))
.
Space Complexity
The space complexity of the given code is O(1)
. Despite the list comprehension inside the sum function, it does not create a new list due to the generator expression; instead, it calculates the sum on the fly. Thus, the only additional space used is for a few variables (left
, right
, mid
, cnt
), which is constant and does not depend on the input size. Therefore, the space used is constant and does not grow with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first