Formatted question description: https://leetcode.ca/all/2171.html

# 2171. Removing Minimum Number of Magic Beans (Medium)

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,,6,5]1Output:4Explanation:- We remove 1 bean from the bag with only 1 bean. This results in the remaining bags: [4,,6,5] - Then we remove 2 beans from the bag with 6 beans. This results in the remaining bags: [4,0,0,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.4

**Example 2:**

Input:beans = [,10,2,3]2Output:7Explanation:- We remove 2 beans from one of the bags with 2 beans. This results in the remaining bags: [,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.0

**Constraints:**

`1 <= beans.length <= 10`

^{5}`1 <= beans[i] <= 10`

^{5}

**Similar Questions**:

## Solution 1. Sorting

Sort the original array `A`

.

If we select `A[i]`

as the number of beans in a non-empty bag, the number of removals needed is `sum(A) - (N - i) * A[i]`

.

**Meaning of equation**

For all `A[j] (j < i)`

, they are completely removed, contributing `A[0] + .. + A[i-1]`

removals.

For all `A[j] (j >= i)`

, they become all `A[i]`

s, contributing `A[i] + .. + A[N-1] - (N-i) * A[i]`

removals.

Summing these two up, we get `sum(A) - (N - i) * A[i]`

.

Another way to think this is to remove every thing and recover `(N - i) * A[i]`

beans that shouldn’t be removed.

**Why we should pick the number from A**

Assume `A = [1,5,10]`

. If we pick a number that is not in `A`

, say `3`

, `A`

becomes `[0,3,3]`

. This is definitely not better than picking `A[i] = 5`

resulting in `[0,5,5]`

. So, a solution picking a non-existent number is always dominated by another solution picking an existing number.

**Example:**

`A = [1,4,5,6]`

, `sum(A) = 16`

- If we pick
`A[0] = 1`

, the result array is`[1,1,1,1]`

, # of removals is`16 - (4 - 0) * 1 = 12`

. - If we pick
`A[1] = 4`

, the result array is`[0,4,4,4]`

, # of removals is`16 - (4 - 1) * 4 = 4`

. - If we pick
`A[2] = 5`

, the result array is`[0,0,5,5]`

, # of removals is`16 - (4 - 2) * 5 = 6`

. - If we pick
`A[3] = 6`

, the result array is`[0,0,0,6]`

, # of removals is`16 - (4 - 3) * 6 = 10`

.

```
// OJ: https://leetcode.com/problems/removing-minimum-number-of-magic-beans/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
long long minimumRemoval(vector<int>& A) {
long N = A.size(), ans = LLONG_MAX, sum = accumulate(begin(A), end(A), 0L);
sort(begin(A), end(A));
for (int i = 0; i < N; ++i) ans = min(ans, sum - (N - i) * A[i]);
return ans;
}
};
```

## Discuss

https://leetcode.com/problems/removing-minimum-number-of-magic-beans/discuss/1766764