LeetCode 6006. Take out the least number of magic beans

6006. Take out the smallest number of magic beans

To give you one just An array of integers beans , Each integer represents the number of magic beans in a bag .

Please... From each bag take out Some beans （ It's fine too Don't take out ）, Make the rest Non empty In the bag （ namely At least also One Magic bean bag ） Number of magic beans equal . Once the magic beans are removed from the bag , You can't put it in any other bag .

Please return to where you need to take out the magic beans Minimum number .

Example 1：

 Input ：beans = [4,1,6,5]
 Output ：4
 explain ：
-  We never had  1  Take it out of a magic bean bag  1  A magic bean .
   The number of magic beans left in the bag is ：[4,0,6,5]
-  Then we have  6  Take it out of a magic bean bag  2  A magic bean .
   The number of magic beans left in the bag is ：[4,0,4,5]
-  Then we have  5  Take it out of a magic bean bag  1  A magic bean .
   The number of magic beans left in the bag is ：[4,0,4,4]
 A total of  1 + 2 + 1 = 4  A magic bean , The number of magic beans left in the non empty bag is equal .
 Nothing is better than taking out  4  A plan with fewer magic beans .

Example 2：

 Input ：beans = [2,10,3,2]
 Output ：7
 explain ：
-  We never had  2  Take it out of one of the bags of magic beans  2  A magic bean .
   The number of magic beans left in the bag is ：[0,10,3,2]
-  Then we have... From another  2  Take it out of a magic bean bag  2  A magic bean .
   The number of magic beans left in the bag is ：[0,10,3,0]
-  Then we have  3  Take it out of a magic bean bag  3  A magic bean .
   The number of magic beans left in the bag is ：[0,10,0,0]
 A total of  2 + 2 + 3 = 7  A magic bean , The number of magic beans left in the non empty bag is equal .
 Nothing is better than taking out  7  A plan with fewer magic beans .

Tips ：

• 1 <= beans.length <= 105
• 1 <= beans[i] <= 105

Two 、 Method 1

Sort + The prefix and

class Solution {
    
    public long minimumRemoval(int[] beans) {
    
        long res = Long.MAX_VALUE;
        long sum = 0;
        Arrays.sort(beans);
        for (int i = 0; i < beans.length; i++) {
    
            sum += beans[i];
        }
        for (int i = 0; i < beans.length; i++) {
    
            long temp = 0;
            temp += sum - (long)(beans.length - i) * beans[i];
            res = Math.min(res, temp);
        }
        return res;

    }
}

Complexity analysis

• Time complexity ：O(nlogn).

• Spatial complexity ：O(1).