# Removing Minimum Number of Magic Beans
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/removing-minimum-number-of-magic-beans)
Canonical: https://scaleengineer.com/dsa/problems/removing-minimum-number-of-magic-beans
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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 <= 105`
* `1 <= beans[i] <= 105`

# Approaches
## Brute Force by Iterating Through Each Bean as Target
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public long minimumRemoval(int[] beans) {
        long minRemoved = Long.MAX_VALUE;
        int n = beans.length;
        if (n <= 1) {
            return 0;
        }

        // Use a Set to consider only unique bean counts as targets to avoid redundant calculations,
        // though the worst-case complexity remains the same.
        java.util.Set<Integer> uniqueBeans = new java.util.HashSet<>();
        for (int bean : beans) {
            uniqueBeans.add(bean);
        }

        for (int target : uniqueBeans) {
            long currentRemoved = 0;
            for (int bean : beans) {
                if (bean < target) {
                    currentRemoved += bean;
                } else {
                    currentRemoved += bean - target;
                }
            }
            minRemoved = Math.min(minRemoved, currentRemoved);
        }
        return minRemoved;
    }
}
```
### 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.

## Optimal Approach using Sorting
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.
**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).
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public long minimumRemoval(int[] beans) {
        int n = beans.length;
        if (n <= 1) {
            return 0;
        }
        
        Arrays.sort(beans);
        
        long totalSum = 0;
        for (int bean : beans) {
            totalSum += bean;
        }
        
        long minRemoved = totalSum; // A valid initial value is removing all beans
        
        for (int i = 0; i < n; i++) {
            // If we make all remaining bags equal to beans[i],
            // there will be (n - i) bags remaining.
            long remainingBeans = (long)(n - i) * beans[i];
            long currentRemoved = totalSum - remainingBeans;
            minRemoved = Math.min(minRemoved, currentRemoved);
        }
        
        return minRemoved;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  long minimumRemoval(int[] beans) {
    Arrays.sort(beans);
    long s = 0;
    for (int v : beans) {
      s += v;
    }
    long ans = s;
    int n = beans.length;
    for (int i = 0; i < n; ++i) {
      ans = Math.min(ans, s - (long)beans[i] * (n - i));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumRemoval(vector<int> &beans) {
    sort(beans.begin(), beans.end());
    long long s = accumulate(beans.begin(), beans.end(), 0ll);
    long long ans = s;
    int n = beans.size();
    for (int i = 0; i < n; ++i)
      ans = min(ans, s - 1ll * beans[i] * (n - i));
    return ans;
  }
};

```

### Python

```python
class 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
```