Removing Minimum Number of Magic Beans

LeetCode 2290 | Difficulty: Medium

Medium

Problem Description

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`

Topics: Array, Greedy, Sorting, Enumeration, Prefix Sum

---

Approach

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 372 ms)

Metric	Value
Runtime	372 ms
Memory	48.9 MB
Date	2022-02-13

Solution

public class Solution {
    public long MinimumRemoval(int[] beans) {
          Array.Sort(beans);
    int len = beans.Length, m = beans.Length;
    long sum = 0;
    foreach (var num in beans)
    {
        sum += num;
    }
    long moves = long.MaxValue;
    for (int i = 0; i < len; i++, m--)
    {
        moves = Math.Min(moves, sum - ((long)m * (long)beans[i]));
    }

    return moves;

    }
}

📜 1 more C# submission(s)

Submission (2022-02-13) — 417 ms, 48.2 MB

public class Solution {
    public long MinimumRemoval(int[] beans) {
          Array.Sort(beans);
    int len = beans.Length;
    long m = beans.Length;
    long sum = 0;
    foreach (var num in beans)
    {
        sum += num;
    }
    long moves = long.MaxValue;
    for (int i = 0; i < len; i++, m--)
    {
        moves = Math.Min(moves, sum - (m * (long)beans[i]));
    }

    return moves;

    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Notice that if we choose to make x bags of beans empty, we should choose the x bags with the least amount of beans.

Hint 2: Notice that if the minimum number of beans in a non-empty bag is m, then the best way to make all bags have an equal amount of beans is to reduce all the bags to have m beans.

Hint 3: Can we iterate over how many bags we should remove and choose the one that minimizes the total amount of beans to remove?

Hint 4: Sort the bags of beans first.