## Problem

## Key Idea

Sort the array `beans`

in ascending order.

We can calculate the minimum beans we should remove in \(O(1)\) time.

ex) `beans`

= [1,4,5,6]

From left to right, calculate `beansToRemove`

value of `beans[i]`

and find minimum value among them.

- Time: \(O(N{\log}N + N)\)
- Space: \(O(1)\)

Note

use type`long long`

to avoid integer overflow.

(Take a look at the constraints.)

## Implementation

```
typedef vector<int> vi;
typedef long long ll;
class Solution {
public:
ll minimumRemoval(vi &beans) {
int n= beans.size();
if (n == 1) return 0;
sort(beans.begin(), beans.end());
ll totalSum= 0;
for (auto bean : beans) totalSum += bean;
ll ans= totalSum;
for (int i=0; i < n; ++i) {
ans= min(ans, totalSum-(n-i)*(beans[i]*1ll));
}
return ans;
}
};
```

## Leave a comment