Question

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

Solution 1: Sorting + Enumeration

We can sort all the beans in the bags in ascending order, and then enumerate the number of beans $beans[i]$ in each bag as the final number of beans in the bag. The total remaining number of beans is $beans[i] \times (n - i)$, so the number of beans that need to be taken out is $s - beans[i] \times (n - i)$, where $s$ is the total number of beans in all bags. We need to find the minimum number of beans that need to be taken out among all schemes.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the number of bags.

class Solution:
  def minimumRemoval(self, beans: List[int]) -> int:
    beans.sort()
    s, n = sum(beans), len(beans)
    return min(s - x * (n - i) for i, x in enumerate(beans))

class Solution {
  public long minimumRemoval(int[] beans) {
    Arrays.sort(beans);
    long s = 0;
    for (int x : beans) {
      s += x;
    }
    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;
  }
};

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

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