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.
The idea is to sort the array and try to make the content of each bag equal to the number of beans in every successive bag. By considering each unique value in the sorted array as a candidate to make all bags equal, we can calculate and minimize the number of beans to be removed using prefix sum. This is efficient because after sorting, all the candidates to make bags equal are in a sequence, which reduces the solution complexity.
The solution sorts the array and computes the total number of beans. Then, using a loop, it calculates the minimum beans that need to be removed by evaluating each unique value in the sorted array as the desired number of beans per bag.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is done in place and only constant extra space is used.
This approach involves using binary search to find the optimal value that can be set as the target for all bags. We perform counting to compute how many beans need to be removed if we choose each bean value as the target. This can allow for a more refined search over possible values without needing to sequentially check each potential number like in the previous approach.
This solution uses binary search through possible target values for beans. For each possible target, it calculates how many beans need to be removed and minimizes this number across potential targets.
Time Complexity: O(n log m + m), for sorting and evaluating each target across a range.
Space Complexity: O(1).
We can sort all the beans in the bags in ascending order, and then enumerate the number of beans beans[i] in each bag as the final number of beans in the bag. The total remaining number of beans is beans[i] times (n - i), so the number of beans that need to be taken out is s - beans[i] times (n - i), where s is the total number of beans in all bags. We need to find the minimum number of beans that need to be taken out among all schemes.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of bags.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Prefix Sum Method | Time Complexity: O(n log n) due to sorting. |
| Binary Search and Counting | Time Complexity: O(n log m + m), for sorting and evaluating each target across a range. |
| Sorting + Enumeration | — |
| 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. |
Removing Minimum Number of Magic Beans | Leetcode 2171 | Contest 280 | TC O(nlogn) SC(1) 🔥🔥 • Coding Decoded • 2,310 views views
Watch 7 more video solutions →Practice Removing Minimum Number of Magic Beans with our built-in code editor and test cases.
Practice on FleetCode