##### Welcome to Subscribe On Youtube

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,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

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

• 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

############

# 2171. Removing Minimum Number of Magic Beans
# https://leetcode.com/problems/removing-minimum-number-of-magic-beans/

class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
beans.sort()
total = sum(beans)
res = float('inf')
n = len(beans)

for i, x in enumerate(beans):
res = min(res, total - (n - i) * x)

return res


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

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

func min(a, b int) int {
if a < b {
return a
}
return b
}

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



## Discuss

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