6006. Take out the minimum number of magic beans

6006. Take out the smallest number of magic beans

The question

An array of positive integers beans, Everyone has beans[i] Bean . Take out some beans from each , Make not 0 The values of bits are the same , Find the minimum number of beans .

---

Examples

Input ：beans = [4,1,6,5]
Output ：4
explain ：

• We never had 1 Take it out of a magic bean bag 1 A magic bean .
  The number of magic beans left in the bag is ：[4,0,6,5]
• Then we have 6 Take it out of a magic bean bag 2 A magic bean .
  The number of magic beans left in the bag is ：[4,0,4,5]
• Then we have 5 Take it out of a magic bean bag 1 A magic bean .
  The number of magic beans left in the bag is ：[4,0,4,4]
  A total of 1 + 2 + 1 = 4 A magic bean , The number of magic beans left in the non empty bag is equal .
  Nothing is better than taking out 4 A plan with fewer magic beans .

Input ：beans = [2,10,3,2]
Output ：7
explain ：

• We never had 2 Take it out of one of the bags of magic beans 2 A magic bean .
  The number of magic beans left in the bag is ：[0,10,3,2]
• Then we have... From another 2 Take it out of a magic bean bag 2 A magic bean .
  The number of magic beans left in the bag is ：[0,10,3,0]
• Then we have 3 Take it out of a magic bean bag 3 A magic bean .
  The number of magic beans left in the bag is ：[0,10,0,0]
  A total of 2 + 2 + 3 = 7 A magic bean , The number of magic beans left in the non empty bag is equal .
  Nothing is better than taking out 7 A plan with fewer magic beans .

---

Ideas

We can beans After sorting from small to large , Enumerate the number of all final non empty beans x, Less than x Empty beans , Greater than x The number of beans decreased to x.

• result ：0000xxxxx, What needs to be removed is ：ans = sum - (len - i) * x;

---

Algorithm

thinking + Sort

---

Code

class Solution {
    
public:
    long long minimumRemoval(vector<int>& beans) {
    
        int len = beans.size();
        long long sum = 0, res;
        for (auto &x: beans) sum += x;
        res = sum;

        sort(beans.begin(), beans.end());
        for (int i = 0; i < len; i++) {
    
            res = min(res, sum - (len - i) * (long long)beans[i]);
        }
        return res;
    }
};

---