{x}
blog image

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.

 

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 <= 105
  • 1 <= beans[i] <= 105

Solution Explanation: Removing Minimum Number of Magic Beans

This problem asks to find the minimum number of beans to remove so that the remaining non-empty bags have an equal number of beans. The optimal approach involves sorting and enumeration.

Algorithm:

  1. Sort: Sort the beans array in ascending order. This allows us to efficiently iterate through potential target bean counts.

  2. Iterate and Calculate: Iterate through the sorted beans array. For each element beans[i], consider it as the target number of beans in each remaining bag.

  3. Removal Calculation: For each beans[i]:

    • The number of bags that will have beans[i] beans is (n - i), where n is the total number of bags.
    • The total number of beans in these bags will be beans[i] * (n - i).
    • The total number of beans initially present is s = sum(beans).
    • The number of beans to remove is s - beans[i] * (n - i).

  4. Minimum Removal: Keep track of the minimum number of beans removed across all iterations. This minimum represents the solution.

Time Complexity: O(n log n), dominated by the sorting step. The iteration takes O(n) time.

Space Complexity: O(log n) or O(1) depending on the sorting implementation. In-place sorting algorithms have O(1) space complexity, while merge sort or other recursive approaches might need O(log n) space for the call stack.

Code Examples:

The code examples below demonstrate the solution in several programming languages. They all follow the same algorithmic steps: sort, iterate, calculate removals, and find the minimum.

Python:

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        s = sum(beans)
        n = len(beans)
        min_removed = s  # Initialize with the maximum possible removal (removing all but one bag)
 
        for i, num_beans in enumerate(beans):
            removed = s - num_beans * (n - i)
            min_removed = min(min_removed, removed)
 
        return min_removed

Java:

import java.util.Arrays;
 
class Solution {
    public long minimumRemoval(int[] beans) {
        Arrays.sort(beans);
        long s = 0;
        for (int bean : beans) s += bean;
        int n = beans.length;
        long minRemoved = s;
 
        for (int i = 0; i < n; i++) {
            long removed = s - (long) beans[i] * (n - i);
            minRemoved = Math.min(minRemoved, removed);
        }
        return minRemoved;
    }
}

C++:

#include <algorithm>
#include <numeric>
#include <vector>
 
using namespace std;
 
class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        sort(beans.begin(), beans.end());
        long long s = accumulate(beans.begin(), beans.end(), 0LL);
        int n = beans.size();
        long long minRemoved = s;
 
        for (int i = 0; i < n; i++) {
            long long removed = s - (long long)beans[i] * (n - i);
            minRemoved = min(minRemoved, removed);
        }
        return minRemoved;
    }
};

JavaScript:

/**
 * @param {number[]} beans
 * @return {number}
 */
var minimumRemoval = function(beans) {
    beans.sort((a, b) => a - b);
    let s = beans.reduce((sum, val) => sum + val, 0);
    let n = beans.length;
    let minRemoved = s;
 
    for (let i = 0; i < n; i++) {
        let removed = s - beans[i] * (n - i);
        minRemoved = Math.min(minRemoved, removed);
    }
    return minRemoved;
};

These examples all implement the same core logic, differing only in syntax and specific library functions used for sorting and summation. The efficiency and correctness remain consistent across all languages.