Watch 8 video solutions for Removing Minimum Number of Magic Beans, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Coding Decoded has 2,310 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag.
Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at least one bean) is equal. Once a bean has been removed from a bag, you are not allowed to return it to any of the bags.
Return the minimum number of magic beans that you have to remove.
Example 1:
Input: beans = [4,1,6,5] Output: 4 Explanation: - We remove 1 bean from the bag with only 1 bean. This results in the remaining bags: [4,0,6,5] - Then we remove 2 beans from the bag with 6 beans. This results in the remaining bags: [4,0,4,5] - Then we remove 1 bean from the bag with 5 beans. This results in the remaining bags: [4,0,4,4] We removed a total of 1 + 2 + 1 = 4 beans to make the remaining non-empty bags have an equal number of beans. There are no other solutions that remove 4 beans or fewer.
Example 2:
Input: beans = [2,10,3,2] Output: 7 Explanation: - We remove 2 beans from one of the bags with 2 beans. This results in the remaining bags: [0,10,3,2] - Then we remove 2 beans from the other bag with 2 beans. This results in the remaining bags: [0,10,3,0] - Then we remove 3 beans from the bag with 3 beans. This results in the remaining bags: [0,10,0,0] We removed a total of 2 + 2 + 3 = 7 beans to make the remaining non-empty bags have an equal number of beans. There are no other solutions that removes 7 beans or fewer.
Constraints:
1 <= beans.length <= 1051 <= beans[i] <= 105Problem Overview: You are given an array where beans[i] represents the number of magic beans in the i-th bag. Remove the minimum number of beans so that every non-empty bag ends up with the same number of beans. Bags can become empty after removals.
Approach 1: Sorting and Prefix Sum Method (O(n log n) time, O(n) space)
The key observation: if the final number of beans per non-empty bag is x, every bag with fewer than x beans must be emptied completely, while bags with more than x beans must be reduced down to x. Start by sorting the array so potential target values appear in increasing order. Build a prefix sum to quickly compute how many beans exist in any prefix. When you choose beans[i] as the target value, all bags before i are removed entirely and all bags after i are trimmed down to beans[i]. The number of beans kept becomes beans[i] * (n - i), so the removed beans equal totalSum - kept. Iterate through all indices and track the minimum removal. This approach relies on sorting and prefix sum to evaluate each candidate efficiently.
Approach 2: Binary Search and Counting (O(n log n) time, O(1)–O(n) space)
Another way to think about the problem is to enumerate possible target bean counts and quickly determine how many bags must be removed or trimmed. After sorting the array, use binary search to locate the first position where the bag count is at least the target value. All earlier bags are emptied. For bags on the right, count how many exceed the target and subtract the excess. This method treats each candidate value as a decision point and uses binary search to find boundaries efficiently. It still relies on sorted order and works well when you want explicit counting logic rather than computing totals directly. The strategy combines array processing with a greedy observation that only existing bag sizes need to be considered as targets.
Recommended for interviews: The sorting + prefix sum solution is the expected approach. Interviewers want to see the greedy insight that the final value must match one of the existing bag sizes and that sorting lets you evaluate each candidate efficiently. A brute-force idea (trying every possible bean count) shows understanding of the constraint, but the prefix-sum optimization demonstrates strong algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Prefix Sum | O(n log n) | O(n) | Best general solution. Efficiently evaluates each possible target bean count. |
| Binary Search and Counting | O(n log n) | O(1)–O(n) | Useful when explicitly finding boundaries of bags to remove using binary search. |