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

Problem

2171. Removing Minimum Number of Magic Beans

Approach

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.

Note
use type long long to avoid integer overflow.
(Take a look at the constraints.)

Code

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

Complexity

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