Leetcode 2226: Maximum Candies Allocated to K Children
You are given a 0-indexed integer array
candies, where each element represents the number of candies in a pile. You also have an integer k, which is the number of children. You need to distribute the candies into k piles such that each child gets the same number of candies. Each child can receive at most one pile, and some piles may go unused. Your task is to return the maximum number of candies each child can receive.Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `candies`, where each element is the size of a pile of candies, and an integer `k`, the number of children.
Example: candies = [7, 4, 10], k = 3
Constraints:
• 1 <= candies.length <= 10^5
• 1 <= candies[i] <= 10^7
• 1 <= k <= 10^12
Output: Return the maximum number of candies each child can receive, such that each child gets the same number of candies.
Example: Output: 4
Constraints:
• The result should be a non-negative integer.
Goal: The goal is to determine the maximum number of candies each child can get, ensuring that each child gets the same number of candies, by distributing the candies from the available piles.
Steps:
• First, calculate the total sum of all candies in the piles.
• Check if the total candies are sufficient to satisfy `k` children.
• Use binary search to find the maximum number of candies each child can get. For each mid value, check if it's possible to divide the piles such that at least `k` children get the same number of candies.
Goal: The input guarantees that the total number of candies is sufficient to attempt distributing to the `k` children.
Steps:
• The number of piles and the number of children are both large, so the solution must be efficient.
Assumptions:
• Each child can receive at most one pile of candies.
• Input: Input: candies = [7, 4, 10], k = 3
• Explanation: In this case, we can divide the candies into piles of size 4 (from the 10 candy pile) and 3 (from the 7 candy pile), leaving one pile of size 4 unused. Each of the three children can then receive 4 candies.
• Input: Input: candies = [1, 2, 3], k = 4
• Explanation: There are only 6 candies, but 4 children need to be satisfied, so it's impossible to give each child at least one candy, and the answer is 0.
Approach: The approach involves using binary search to find the maximum number of candies each child can get. We first calculate the total number of candies and use binary search to explore the possible values of the number of candies each child can get. For each value, we check if it's possible to divide the candies such that at least `k` children receive that number.
Observations:
• Binary search is useful for finding the maximum value in this type of optimization problem.
• Start with the total sum of candies and search for the maximum possible number of candies each child can get using binary search.
Steps:
• 1. Compute the total number of candies from the `candies` array.
• 2. Use binary search on the possible values for the maximum number of candies each child can get, ranging from 1 to the largest pile.
• 3. For each mid value in binary search, check if it's possible to divide the piles such that `k` children can each receive that number of candies.
• 4. Return the largest feasible value.
Empty Inputs:
• If the `candies` array is empty, the result is 0 since there are no candies to distribute.
Large Inputs:
• The solution should handle cases where `candies.length` is large (up to 100,000) and `k` can be as large as 10^12 efficiently.
Special Values:
• If the total number of candies is less than `k`, return 0 since it's impossible to satisfy all children.
Constraints:
• The solution should optimize for time complexity to handle the large input sizes.
bool can(vector<int>& candies, long long kids, int per) {
long long cnt = 0;
for(int i = 0; i < candies.size(); i++) {
if(candies[i] < per) continue;
int tmp = candies[i];
cnt+= tmp/per;
}
return cnt >= kids;
}
int maximumCandies(vector<int>& candies, long long k) {
long long sum = accumulate(candies.begin(), candies.end(), 0L);
if(sum < k) return 0;
int l = 1, r = *max_element(candies.begin(), candies.end());
int ans = 0;
while(l <= r) {
int mid = l + (r - l + 1) / 2;
if(can(candies, k, mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
1 : Function Declaration
bool can(vector<int>& candies, long long kids, int per) {
The `can` function is declared, which checks whether it's possible to distribute `per` candies to `kids` based on the number of candies available.
2 : Variable Initialization
long long cnt = 0;
A variable `cnt` is initialized to 0 to keep track of how many kids can receive at least `per` candies.
3 : Loop
for(int i = 0; i < candies.size(); i++) {
A loop iterates through each candy count in the `candies` vector to determine how many candies can be given to the kids.
4 : Condition Check
if(candies[i] < per) continue;
If a particular candy count is less than `per`, the loop skips that entry as it cannot be used to distribute to a kid.
5 : Variable Assignment
int tmp = candies[i];
The number of candies available in the current iteration is assigned to the variable `tmp`.
6 : Candy Distribution
cnt+= tmp/per;
The number of kids that can receive `per` candies from the current candy count (`tmp`) is added to `cnt`.
7 : Return Statement
return cnt >= kids;
The function returns `true` if the total number of kids that can receive at least `per` candies is greater than or equal to the number of kids (`k`). Otherwise, it returns `false`.
8 : Function Declaration
int maximumCandies(vector<int>& candies, long long k) {
The `maximumCandies` function is declared, which uses binary search to determine the maximum number of candies that can be distributed equally to the kids.
9 : Variable Initialization
long long sum = accumulate(candies.begin(), candies.end(), 0L);
The variable `sum` is initialized with the total sum of candies available by accumulating all elements in the `candies` vector.
10 : Condition Check
if(sum < k) return 0;
If the total number of candies is less than the number of kids, the function returns 0 as it's impossible to distribute candies.
11 : Variable Initialization
int l = 1, r = *max_element(candies.begin(), candies.end());
Two variables `l` and `r` are initialized to represent the lower and upper bounds for binary search. `l` starts at 1, and `r` is set to the maximum value in the `candies` vector.
12 : Variable Initialization
int ans = 0;
The variable `ans` is initialized to 0 to store the maximum number of candies that can be distributed equally to all kids.
13 : Binary Search Loop
while(l <= r) {
A while loop is used to perform binary search between the lower and upper bounds (`l` and `r`) to find the optimal number of candies per kid.
14 : Binary Search Calculation
int mid = l + (r - l + 1) / 2;
The midpoint `mid` is calculated to check how many candies can be distributed equally to all the kids.
15 : Condition Check
if(can(candies, k, mid)) {
If the `can` function returns `true` for the midpoint number of candies, it means it's possible to distribute candies equally to all the kids.
16 : Update Result
ans = mid;
If the distribution is possible, the `ans` variable is updated to store the current `mid` value, which represents the maximum candies that can be distributed to each kid.
17 : Binary Search Update
l = mid + 1;
The lower bound `l` is updated to `mid + 1` to search for larger values in the next iteration of the binary search.
18 : Else Condition
} else {
If the `can` function returns `false`, it means the current `mid` value is too large, and we need to search for smaller values.
19 : Binary Search Update
r = mid - 1;
The upper bound `r` is updated to `mid - 1` to search for smaller values in the next iteration of the binary search.
20 : Return Statement
return ans;
The function returns the maximum number of candies that can be distributed equally to the kids.
Best Case: O(n log(max(candies[i])))
Average Case: O(n log(max(candies[i])))
Worst Case: O(n log(max(candies[i])))
Description: The binary search process runs in `log(max(candies[i]))` time, and for each search step, we calculate the possible piles which takes linear time O(n).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we only use a few variables and do not require additional space proportional to the input size.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus