competitive-programmingMar 3, 20221 min read

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

Updated: Mar 3, 2022

MathSortings

Available in:enko

#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)$