2171. Removing Minimum Number of Magic Beans

You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag.

Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at least one bean) is equal. Once a bean has been removed from a bag, you are not allowed to return it to any of the bags.

Return the minimum number of magic beans that you have to remove.

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        long long remainingBean = 0, n = beans.size();
        long long dropBeans = 0, upperBeanCnt = n;
        map<long long, long long> beanCount;
        for(int i = 0; i < n; i++) {
            remainingBean += beans[i];
            beanCount[beans[i]]++;
        }
        long long res = remainingBean;
        for(auto [bean, cnt] : beanCount) {
            upperBeanCnt -= cnt;
            remainingBean -= bean * cnt;
            res = min(res, dropBeans + remainingBean - upperBeanCnt * bean);
            dropBeans += bean * cnt;
        }
        return res;
    }
};