Removing Minimum Number of Magic Beans

Med

#1978Time: O(N^2), where N is the number of bags. For each of the N potential targets (at most), we iterate through all N bags to calculate the cost.Space: O(N) in the provided snippet due to the use of a HashSet to store unique bean values. A version without the HashSet would have O(1) space complexity.1 company

Patterns

Greedy Enumeration Prefix Sum

Algorithms

Sorting

Data structures

Array

Companies

DE Shaw

Prompt

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 <= 10⁵
1 <= beans[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward brute-force approach is to test every possible outcome. The key observation is that to minimize removals, the final equal number of beans in non-empty bags must be one of the initial values from the beans array. If we were to choose a target value T that is not in the original array, we could always adjust T to the next highest value present in the array and reduce the number of removed beans. Therefore, we only need to check each beans[i] as a potential target value.

Algorithm

Initialize minRemoved to a very large value (e.g., Long.MAX_VALUE).
Iterate through each element beans[i] in the input array. This beans[i] will be considered as the target value.
For each target, initialize a currentRemoved counter to zero.
Start a nested loop to iterate through every element beans[j] in the array.
Inside the nested loop, calculate the beans to remove for beans[j] based on the target:
- If beans[j] < target, all beans[j] must be removed. Add beans[j] to currentRemoved.
- If beans[j] >= target, beans[j] - target beans must be removed. Add this value to currentRemoved.
After the inner loop finishes, currentRemoved holds the total cost for the chosen target. Compare it with minRemoved and update minRemoved if currentRemoved is smaller.
After the outer loop finishes, minRemoved will hold the minimum possible number of beans to remove.

Walkthrough

The algorithm iterates through each element of the beans array, treating it as the potential target value T for all non-empty bags. For each chosen target, we perform a second loop through the entire beans array to calculate the total number of beans that would need to be removed. If a bag b has fewer beans than target, all b beans are removed. If a bag b has more or equal beans than target, b - target beans are removed. We sum these removals to get the cost for the current target. The minimum cost found across all possible targets is the answer.

1class Solution {2    public long minimumRemoval(int[] beans) {3        long minRemoved = Long.MAX_VALUE;4        int n = beans.length;5        if (n <= 1) {6            return 0;7        }8 9        // Use a Set to consider only unique bean counts as targets to avoid redundant calculations,10        // though the worst-case complexity remains the same.11        java.util.Set<Integer> uniqueBeans = new java.util.HashSet<>();12        for (int bean : beans) {13            uniqueBeans.add(bean);14        }15 16        for (int target : uniqueBeans) {17            long currentRemoved = 0;18            for (int bean : beans) {19                if (bean < target) {20                    currentRemoved += bean;21                } else {22                    currentRemoved += bean - target;23                }24            }25            minRemoved = Math.min(minRemoved, currentRemoved);26        }27        return minRemoved;28    }29}

Complexity

Time

O(N^2), where N is the number of bags. For each of the N potential targets (at most), we iterate through all N bags to calculate the cost.

Space

O(N) in the provided snippet due to the use of a HashSet to store unique bean values. A version without the HashSet would have O(1) space complexity.

Trade-offs

Pros

The logic is simple to understand and implement directly from the problem definition.
It correctly identifies that the optimal target must be one of the existing bean values.

Cons

The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5), and this solution will result in a 'Time Limit Exceeded' error on most platforms.

This optimal approach significantly improves performance by sorting the input array first. After sorting, we can calculate the cost for each potential target value much more efficiently. Instead of recalculating the sum of removals each time, we use a clever mathematical simplification. The total number of beans to be removed is simply the initial total number of beans minus the number of beans that will remain after the operation. This avoids the nested loop structure of the brute-force approach.

Algorithm

Sort the beans array in non-decreasing order.
Calculate totalSum, the sum of all elements in beans. This can be done in a single pass.
Initialize minRemoved to totalSum (which is the cost of removing all beans, a valid scenario).
Let n be the length of the beans array.
Iterate through the sorted array with index i from 0 to n-1.
In each iteration, beans[i] is the candidate for the final target value.
The number of bags that will remain non-empty is n - i (all bags from index i to n-1).
The total number of beans remaining in these bags will be (long)(n - i) * beans[i]. A long cast is crucial to prevent integer overflow.
The number of beans removed for this target is totalSum - remainingBeans.
Update minRemoved = Math.min(minRemoved, currentRemoved).
After the loop, return minRemoved.

Walkthrough

First, we sort the beans array. This allows us to process potential targets in increasing order. We also pre-calculate the totalSum of all beans. Then, we iterate through the sorted beans array. For each element beans[i], we consider it as the target value T. If beans[i] is the target, all bags with an initial count less than beans[i] (i.e., beans[0] to beans[i-1]) must be emptied. All bags with an initial count greater than or equal to beans[i] (i.e., beans[i] to beans[n-1]) will be made to have beans[i] beans. The number of bags that will remain non-empty is n - i. The total number of beans remaining will be (n - i) * beans[i]. Therefore, the number of beans removed is totalSum - (n - i) * beans[i]. We calculate this cost for each beans[i] as the target and find the minimum among them.

1import java.util.Arrays;2 3class Solution {4    public long minimumRemoval(int[] beans) {5        int n = beans.length;6        if (n <= 1) {7            return 0;8        }9        10        Arrays.sort(beans);11        12        long totalSum = 0;13        for (int bean : beans) {14            totalSum += bean;15        }16        17        long minRemoved = totalSum; // A valid initial value is removing all beans18        19        for (int i = 0; i < n; i++) {20            // If we make all remaining bags equal to beans[i],21            // there will be (n - i) bags remaining.22            long remainingBeans = (long)(n - i) * beans[i];23            long currentRemoved = totalSum - remainingBeans;24            minRemoved = Math.min(minRemoved, currentRemoved);25        }26        27        return minRemoved;28    }29}

Complexity

Time

O(N log N), where N is the number of bags. The sorting step dominates the complexity. The subsequent loop to calculate costs runs in O(N) time.

Space

O(log N) or O(N), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log N).

Trade-offs

Pros

Highly efficient with a time complexity of O(N log N), which is optimal for the given constraints.
The formula for calculating removals is concise and avoids the expensive nested loops of the brute-force method.

Cons

The solution requires sorting the array, which has a time complexity of O(N log N).
Care must be taken with potential integer overflows when calculating (n - i) * beans[i], as both n and beans[i] can be up to 10^5. Using a 64-bit integer type (long in Java) is necessary.

Solutions

Solution

1class Solution {2public3  long minimumRemoval(int[] beans) {4    Arrays.sort(beans);5    long s = 0;6    for (int v : beans) {7      s += v;8    }9    long ans = s;10    int n = beans.length;11    for (int i = 0; i < n; ++i) {12      ans = Math.min(ans, s - (long)beans[i] * (n - i));13    }14    return ans;15  }16}

1class Solution {2public:3  long long minimumRemoval(vector<int> &beans) {4    sort(beans.begin(), beans.end());5    long long s = accumulate(beans.begin(), beans.end(), 0ll);6    long long ans = s;7    int n = beans.size();8    for (int i = 0; i < n; ++i)9      ans = min(ans, s - 1ll * beans[i] * (n - i));10    return ans;11  }12};

1class Solution : def minimumRemoval ( self , beans : List [ int ]) -> int : beans . sort () ans = s = sum ( beans ) n = len ( beans ) for i , v in enumerate ( beans ): ans = min ( ans , s - v * ( n - i )) return ans

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