# 2171. Removing Minimum Number of Magic Beans

## Description

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

## Solutions

• 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;
}
}

• 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;
}
};

• 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


• func minimumRemoval(beans []int) int64 {
sort.Ints(beans)
s := 0
for _, v := range beans {
s += v
}
ans := s
n := len(beans)
for i, v := range beans {
ans = min(ans, s-v*(n-i))
}
return int64(ans)
}

• function minimumRemoval(beans: number[]): number {
const n = beans.length;
let sum = beans.reduce((a, c) => a + c, 0);
beans.sort((a, b) => a - b);
let ans = sum;
for (let i = 0; i < n; i++) {
let num = beans[i];
ans = Math.min(sum - num * (n - i), ans);
}
return ans;
}