Leetcode 2171 removing minimum number of magic beans (prefix and recommendation)

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.

Example 1:

Input: beans = [4,1,6,5]
Output: 4
Explanation: 
- We remove 1 bean from the bag with only 1 bean.
  This results in the remaining bags: [4,0,6,5]
- Then we remove 2 beans from the bag with 6 beans.
  This results in the remaining bags: [4,0,4,5]
- Then we remove 1 bean from the bag with 5 beans.
  This results in the remaining bags: [4,0,4,4]
We removed a total of 1 + 2 + 1 = 4 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that remove 4 beans or fewer.

Example 2:

Input: beans = [2,10,3,2]
Output: 7
Explanation:
- We remove 2 beans from one of the bags with 2 beans.
  This results in the remaining bags: [0,10,3,2]
- Then we remove 2 beans from the other bag with 2 beans.
  This results in the remaining bags: [0,10,3,0]
- Then we remove 3 beans from the bag with 3 beans. 
  This results in the remaining bags: [0,10,0,0]
We removed a total of 2 + 2 + 3 = 7 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that removes 7 beans or fewer.

Constraints:

• 1 <= beans.length <= 10^5
• 1 <= beans[i] <= 10^5

Topic link ：https://leetcode.com/problems/removing-minimum-number-of-magic-beans/

The main idea of the topic ： Each basket has n Items , You can take out several items at will , Ask at least how many items you can take out to make the number of items in the non empty basket the same

Topic analysis ： The general idea is to enumerate each number , Calculate the total number of items to be taken out when the current number is used as the final number of items in the basket , Because the amount of data is only 10^5, The frequency of occurrence of each number can be calculated directly from the array frq, Then calculate the prefix value and sum And the number of prefixes and cnt, For numbers num, Anything smaller should obviously be removed , namely sum[num - 1], The larger part is bigger than it sum[N] - sum[num] (N Is the total length ), If all values in this part are num, Then the sum is num * (cnt[N] - cnt[num]), So you want all of these values to be num, A total of sum[N] - sum[num] - num * (cnt[N] - cnt[num]) So many items , Plus less than num Take out all the parts , We can O(1) Calculate the final number of solutions with each number , Take the minimum

26ms, Time beats 99.45%

class Solution {
    final int N = 100000;

    long[] frq = new long[N + 5];
    long[] sum = new long[N + 5];
    long[] cnt = new long[N + 5];
    
    public long minimumRemoval(int[] beans) {
        for (int num : beans) {
            frq[num]++;
        }
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + i * frq[i];
            cnt[i] = cnt[i - 1] + frq[i];
        }
        long ans = Long.MAX_VALUE;
        for (int num : beans) {
            ans = Math.min(ans, magic(num));
        }
        return ans;
    }
    
    private long magic(int num) {
        return sum[num - 1] + sum[N] - sum[num] - num * (cnt[N] - cnt[num]);
    }
}