Problem

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 theminimum number of magic beans that you have to remove.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


    
    
    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

Solution

Method 1 - Sort and Prefix Sum

Intuition

To minimize the number of beans removed, we want to keep all bags with at least x beans (for some x) and remove all beans from bags with less than x. For each possible x (each unique value in beans), calculate the cost to make all non-empty bags have x beans.

Approach

  1. Sort the beans array.
  2. For each index i, if we keep all bags from i to end (all with at least beans[i]), the cost is total_sum - beans[i] * (n - i).
  3. Take the minimum over all i.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

long long minimumRemoval(vector<int>& beans) {
    sort(beans.begin(), beans.end());
    long long total = accumulate(beans.begin(), beans.end(), 0LL);
    long long res = total;
    int n = beans.size();
    for (int i = 0; i < n; ++i) {
        res = min(res, total - 1LL * beans[i] * (n - i));
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import "sort"
func minimumRemoval(beans []int) int64 {
    sort.Ints(beans)
    var total int64
    for _, v := range beans {
        total += int64(v)
    }
    res := total
    n := len(beans)
    for i, v := range beans {
        rem := total - int64(v)*(int64(n-i))
        if rem < res {
            res = rem
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
public class Solution {
    public long minimumRemoval(int[] beans) {
        Arrays.sort(beans);
        long total = 0;
        for (int b : beans) total += b;
        long res = total;
        int n = beans.length;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, total - (long)beans[i] * (n - i));
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

fun minimumRemoval(beans: IntArray): Long {
    beans.sort()
    val total = beans.map { it.toLong() }.sum()
    var res = total
    val n = beans.size
    for (i in beans.indices) {
        res = minOf(res, total - beans[i].toLong() * (n - i))
    }
    return res
}
1
2
3
4
5

def minimumRemoval(beans):
    beans.sort()
    total = sum(beans)
    n = len(beans)
    return min(total - beans[i] * (n - i) for i in range(n))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

fn minimum_removal(mut beans: Vec<i64>) -> i64 {
    beans.sort();
    let total: i64 = beans.iter().sum();
    let n = beans.len() as i64;
    let mut res = total;
    for (i, &b) in beans.iter().enumerate() {
        let rem = total - b * (n - i as i64);
        if rem < res {
            res = rem;
        }
    }
    res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function minimumRemoval(beans: number[]): number {
    beans.sort((a, b) => a - b);
    const total = beans.reduce((a, b) => a + b, 0);
    const n = beans.length;
    let res = total;
    for (let i = 0; i < n; i++) {
        res = Math.min(res, total - beans[i] * (n - i));
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(N log N), where N is the length of beans (for sorting).
  • 🧺 Space complexity: O(1) (ignoring sort space).