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