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 typelong 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