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

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

2171 - Removing Minimum Number of Magic Beans

2171. Removing Minimum Number of Magic Beans (Medium)

Solution 1. Sorting

Discuss

All Problems

All Solutions

Welcome to Subscribe On Youtube

2171. Removing Minimum Number of Magic Beans (Medium)

Solution 1. Sorting

Discuss

All Problems

All Solutions