Apple Redistribution into Boxes
Understanding the Problem
We have packs of apples and boxes with given capacities, and we want to fit every apple using as few boxes as possible.
Apples from the same pack can be split across different boxes. Because of this, individual pack sizes are irrelevant: a selection of boxes works whenever its combined capacity is at least the total number of apples. The problem reduces to finding the smallest set of boxes whose capacities sum to at least that total.
Key Constraints:
1 <= n, m <= 50→ Sorting 50 elements costs nothing, so an O(m log m) solution is comfortable. The bound matters in the other direction for brute force: 2^50 subsets is too many to enumerate when the answer requires most of the boxes.1 <= apple[i], capacity[j] <= 50→ Every sum stays at or below 50 × 50 = 2500, so 32-bit integers are safe and there are no negative values to handle.- The input guarantees a valid redistribution exists, so there is no impossible case to detect and no -1 to return.
Approach 1: Brute Force (Check All Subsets)
Intuition
Try every combination of boxes. For each subset size k, starting from k = 1, test whether some subset of k boxes has combined capacity at least the apple total. Because sizes are tried in increasing order, the first k with a valid subset is the minimum.
The recursive helper builds subsets one box at a time and stops as soon as the running capacity reaches the target, but that early exit only helps when a small subset suffices. When the answer needs most of the boxes, the search still enumerates every subset of each failing size.
Algorithm
- Compute the total number of apples across all packs.
- For each subset size k from 1 to m, search for a subset of k boxes whose capacities sum to at least the total.
- Return the first k for which such a subset exists.
Example Walkthrough
Code
- Time Complexity: O(2^m). In the worst case, we examine all subsets of the capacity array. For m boxes, there are 2^m subsets.
- Space Complexity: O(m). The recursion depth is at most m, so the call stack uses O(m) space.
The subset search does far more work than necessary. A larger box always covers more of the apple total than a smaller one, so there is never a reason to select a smaller box while a larger one sits unused. Sorting the boxes by capacity and taking them from largest to smallest replaces the exponential search with a single pass.
Approach 2: Greedy with Sorting (Optimal)
Intuition
Since apples can be split freely across boxes, only the combined capacity of the chosen boxes matters. To reach the apple total with the fewest selections, take the box with the largest capacity at every step: any smaller choice covers less of the total and can only force more boxes later.
Sort the capacities in descending order, then accumulate them until the running sum meets or exceeds the total number of apples. The number of boxes added at that point is the answer.
Suppose an optimal selection of k boxes leaves out the largest box. Swapping any selected box for the largest one keeps the count at k and can only increase the combined capacity, so the new selection still holds all the apples. Repeating the swap shows that whenever any selection of size k is valid, the k largest boxes also form a valid selection. Scanning boxes from largest to smallest therefore finds the smallest valid k. This style of proof is called an exchange argument.
Algorithm
- Compute the total number of apples by summing the
applearray. - Sort the
capacityarray in descending order. - Initialize a running sum of capacity to 0.
- Iterate through the sorted capacities, adding each to the running sum.
- As soon as the running sum reaches or exceeds the total apples, return the number of boxes used.
Example Walkthrough
Code
- Time Complexity: O(n + m log m). Summing the apple array takes O(n). Sorting the capacity array takes O(m log m). The greedy scan is O(m).
- Space Complexity: O(1) extra space beyond sorting. The scan uses a few variables; the in-place sort itself uses up to O(log m) stack.