Maximum Candies Allocated to K Children

Med

#2029Time: O(N * M), where `N` is the number of piles (`candies.length`) and `M` is the maximum number of candies in a single pile. The outer loop runs up to `M` times, and the inner loop runs `N` times. This is too slow for the given constraints and will result in a Time Limit Exceeded error.Space: O(1), as we only use a few variables to store the counts and loop indices.

Algorithms

Binary Search

Data structures

Array

Prompt

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.

Example 1:

Input: 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.

Example 2:

Input: 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.

Constraints:

1 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁷
1 <= k <= 10¹²

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible value for the number of candies, c, that each child can receive. We want to find the maximum c, so it's logical to start checking from the highest possible value downwards. The highest possible value for c cannot exceed the size of the largest candy pile.

Algorithm

Find the maximum value max_val in the candies array.
Loop for c from max_val down to 1.
Inside the loop, initialize a counter satisfied_children = 0.
Iterate through each pile in the candies array.
Add pile / c to satisfied_children.
After iterating through all piles, check if satisfied_children >= k.
If it is, c is the maximum possible answer. Return c.
If the loop finishes, it means no c >= 1 is possible. Return 0.

Walkthrough

The algorithm iterates through all possible answers for the number of candies, c, starting from a maximum possible value down to 1. The maximum possible value for c is the largest pile in the candies array, as we cannot give a child more candies than what's available in any single pile. For each value of c, we check if it's possible to provide c candies to k children. This is done by calculating how many children can be satisfied from all piles combined. For a pile of size p, we can create p / c sub-piles of size c. We sum this value over all piles. If the total number of children we can satisfy is greater than or equal to k, we have found a valid c. Since we are iterating downwards, the first c we find will be the maximum possible. We can immediately return this value. If the loop completes without finding any valid c (i.e., we check all the way down to 1 and none work), it means it's impossible to give even one candy to each child. In this case, the answer is 0.

1class Solution {2    public int maximumCandies(int[] candies, long k) {3        int maxCandiesInPile = 0;4        for (int c : candies) {5            maxCandiesInPile = Math.max(maxCandiesInPile, c);6        }7 8        // Iterate from the max possible answer downwards9        for (int c = maxCandiesInPile; c >= 1; c--) {10            long childrenCanGet = 0;11            for (int pile : candies) {12                childrenCanGet += pile / c;13            }14            if (childrenCanGet >= k) {15                return c; // Found the largest possible value16            }17        }18 19        return 0; // Cannot even give 1 candy to each child20    }21}

Complexity

Time

O(N * M), where `N` is the number of piles (`candies.length`) and `M` is the maximum number of candies in a single pile. The outer loop runs up to `M` times, and the inner loop runs `N` times. This is too slow for the given constraints and will result in a Time Limit Exceeded error.

Space

O(1), as we only use a few variables to store the counts and loop indices.

Trade-offs

Pros

The logic is straightforward and easy to implement.

Cons

Extremely inefficient due to the large search space for the number of candies.
Will not pass the time limits for the given constraints.

A more efficient approach utilizes binary search on the possible answer. The core observation is that the problem has a monotonic property: if we can give c candies to each of the k children, we can also certainly give c-1 candies. Conversely, if we cannot give c candies, we also cannot give c+1 candies. This monotonicity allows us to binary search for the maximum possible value of c.

Algorithm

Initialize low = 1, high = 10^7 (a safe upper bound for the answer), and ans = 0.
Start a while loop that continues as long as low <= high.
Calculate mid = low + (high - low) / 2.
Check if it's possible to give mid candies to k children:
- Initialize children_count = 0L.
- For each pile in candies, add pile / mid to children_count.
- If children_count >= k, it's possible.
If it's possible to give mid candies:
- This mid is a potential answer. Store it: ans = mid.
- Try for a larger answer: low = mid + 1.
If it's not possible:
- mid is too large. Try for a smaller answer: high = mid - 1.
After the loop terminates, ans holds the maximum number of candies. Return ans.

Walkthrough

We define a search space for the answer c. The minimum possible answer is 0, and the maximum is bounded by the largest candy pile (or 10^7 from the constraints). Let's set our search range from low = 1 to high = 10^7. The answer 0 can be handled as the default if no solution c >= 1 is found. We apply a standard binary search algorithm. In each step, we pick a mid value from the current range [low, high]. We then have a helper function, can_give(c), which checks if it's possible to give c candies to k children. This function iterates through all candy piles and sums up the number of children that can be satisfied: total_children = sum(pile / c). It returns true if total_children >= k, and false otherwise. Note that total_children can be large, so it should be a long. If can_give(mid) is true, it means mid is a possible answer. Since we want to maximize the answer, we store mid as a potential result and try to find an even larger value by searching in the right half of the range: low = mid + 1. If can_give(mid) is false, it means mid is too large. We must reduce the number of candies, so we search in the left half: high = mid - 1. The binary search continues until low > high. The last successfully recorded mid value will be our maximum possible answer.

1class Solution {2    public int maximumCandies(int[] candies, long k) {3        int low = 1;4        int high = 10_000_000; // Max value of candies[i]5        int ans = 0;6 7        while (low <= high) {8            int mid = low + (high - low) / 2;9            10            // mid can't be 0 in this loop setup, but as a safeguard11            if (mid == 0) {12                low = 1;13                continue;14            }15 16            if (canGive(candies, k, mid)) {17                // mid is a possible answer, try for a larger one18                ans = mid;19                low = mid + 1;20            } else {21                // mid is too large, try a smaller one22                high = mid - 1;23            }24        }25        return ans;26    }27 28    // Helper function to check if we can give 'c' candies to 'k' children29    private boolean canGive(int[] candies, long k, int c) {30        long childrenCount = 0;31        for (int pile : candies) {32            childrenCount += (long) pile / c;33        }34        return childrenCount >= k;35    }36}

Complexity

Time

O(N * log(M)), where `N` is `candies.length` and `M` is the maximum possible value of the answer (the search space size, e.g., `10^7`). The binary search takes `log(M)` steps, and each step involves iterating through the `N` piles, taking `O(N)` time.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

Very efficient and guaranteed to pass within the time limits.
It's the optimal way to solve problems with this monotonic property.

Cons

The concept of binary searching on the answer might be slightly less intuitive than a direct brute-force approach.

Solutions

Solution

1class Solution {2public3  int maximumCandies(int[] candies, long k) {4    int left = 0, right = (int)1 e7;5    while (left < right) {6      int mid = (left + right + 1) >> 1;7      long cnt = 0;8      for (int v : candies) {9        cnt += v / mid;10      }11      if (cnt >= k) {12        left = mid;13      } else {14        right = mid - 1;15      }16    }17    return left;18  }19}

1class Solution {2public:3  int maximumCandies(vector<int> &candies, long long k) {4    int left = 0, right = 1e7;5    while (left < right) {6      int mid = (left + right + 1) >> 1;7      long long cnt = 0;8      for (int &v : candies)9        cnt += v / mid;10      if (cnt >= k)11        left = mid;12      else13        right = mid - 1;14    }15    return left;16  }17};

1class Solution:2    def maximumCandies(self, candies: List[int], k: int) -> int: left, right = 0, max(candies) while left < right: mid = (left + right + 1) >> 1 cnt = sum(v // mid for v in candies) if cnt >= k: left = mid else: right = mid - 1 return left

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem