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] <= 105The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log m + m), for sorting and evaluating each target across a range.
Space Complexity: O(1).
| 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. |
How to EASILY solve LeetCode problems • NeetCode • 427,724 views views
Watch 9 more video solutions →Practice Removing Minimum Number of Magic Beans with our built-in code editor and test cases.
Practice on FleetCode