[LeetCode] 2171. Removing Minimum Number of Magic Beans explained

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;
    }
};