2171

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:

• Minimum Moves to Equal Array Elements II (Medium)
• Minimum Operations to Reduce X to Zero (Medium)

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/
// Author: github.com/lzl124631x
// 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