2171. Removing Minimum Number of Magic Beans #

Problem #

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^5
• 1 <= beans[i] <= 10^5

Problem Summary #

You are given a positive integer array beans, where each integer represents the number of magic beans in a bag.

Please take out some beans from each bag (possibly none) so that the number of magic beans in each remaining non-empty bag (that is, a bag with at least one magic bean left) is equal. Once a magic bean is taken out of a bag, you cannot put it into any other bag. Return the minimum number of magic beans you need to take out.

Constraints:

• 1 <= beans.length <= 10^5
• 1 <= beans[i] <= 10^5

Solution Approach #

• There is no particularly clever method for this problem. The initial idea comes from a brute-force solution. Starting from the first bag, use the number of beans in each bag as the baseline in turn, and change the number of beans in the other bags so that the other bags have the same number of beans as the baseline bag.
• If we scan from index 0 to index n-1, there will be a lot of repeated computation. Some interval-sum operations are computed many times repeatedly, making the algorithm inefficient. Since the number of beans removed is strongly related to the number of beans in the baseline bag, sort first. If the number of beans in a bag is less than that of the baseline bag, 0 ≤ j < i, then the number of beans in these bags will become zero. We need to remove beans[0] + beans[1] + ... + beans[i-1] beans; if the number of beans in a bag is greater than or equal to that of the baseline bag, j ≥ i, then the beans in these bags need to be adjusted to beans[i]. We need to remove (beans[i] - beans[i]) + (beans[i+1] - beans[i]) + (beans[i+2] - beans[i]) + ... + (beans[n-1] - beans[i]) = beans[i]+ ... + beans[n-1] - (n-i) * beans[i] beans. Combining these two cases, the total number of beans that need to be removed is sum(beans) - (N - i) * beans[i]. In summary, sort first, then scan the array from small to large, dynamically maintaining the minimum number of beans to remove.

Code #

package leetcode

import "sort"

func minimumRemoval(beans []int) int64 {
	sort.Ints(beans)
	sum, mx := 0, 0
	for i, v := range beans {
		sum += v
		mx = max(mx, (len(beans)-i)*v)
	}
	return int64(sum - mx)
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}