MediumArrayGreedySortingEnumerationPrefix SumUpdated Sep 2026

2171. Removing Minimum Number of Magic Beans

Asked at DE Shaw

Difficulty

Medium

Time

O(n log n)

Space

O(1) extra

Pattern

Array

Companies

1

Problem

You have a list of bags, and beans[i] is how many magic beans are in bag i. You may take beans out of any bags. You may not put beans back.

After you finish, every bag that still has at least one bean must hold exactly the same number of beans. Bags you empty completely are allowed — they just do not count as non-empty bags. Your goal is to remove as few beans as possible.

Return the minimum total number of beans you must remove to reach that state.

Make all non-empty bags equal

beans41650123Start: four bags with 4, 1, 6 and 5 beans.after40440123Empty the 1, trim 6 and 5 down to 4 — every non-emptybag now holds 4, and 4 beans were removed.
We may empty small bags and trim big ones, but every bag left with beans must end up with the same count.

Constraints

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

Examples

Example 1
Inputbeans = [4,1,6,5]
Output4
WhyEmpty the bag of 1 (remove 1 bean). Then trim 6 down to 4 (remove 2) and 5 down to 4 (remove 1). The non-empty bags all hold 4. Total removed = 1 + 2 + 1 = 4.
Example 2
Inputbeans = [2,10,3,2]
Output7
WhyKeep only the bag of 10 and empty everything else: remove 2, 2 and 3 beans. Total removed = 7. Any target smaller than 10 would force trimming the big bag and cost more.

Asked At

1 companies
CompanyDifficulty
DE ShawMediumView all DE Shaw questions →

How to Think About It

1

The final common count should be one of the original bag sizes — any other value removes strictly more beans than rounding it up to the next bag size.

2

Key insight: sort the bags. If the target is beans[i], every bag before i is emptied and every bag from i onward is trimmed to beans[i]. The beans kept are beans[i] * (n - i).

3

Removed beans = total - beans[i] * (n - i). Minimize removal by maximizing kept beans.

4

Walkthrough for [4,1,6,5]: sorted [1,4,5,6], total 16. Kept: 1*4 = 4, 4*3 = 12, 5*2 = 10, 6*1 = 6. Best kept 12 -> removed 4.

5

Use 64-bit integers: 10^5 bags of 10^5 beans each sum to 10^10.

Optimal Approach

Step 1: Sort beans; total = sum(beans).
Step 2: kept = max(beans[i] * (n - i) for i in range(n)).
Step 3: Return total - kept.

Time: O(n log n). Space: O(1) extra.

Sort, then try each bag size as the target

sortedkept = 4 * 3 = 1214560123iTarget = 4: bag 1 is emptied, bags 4, 5, 6 are trimmedto 4, so 12 beans are kept.kept = beans[i] * (n - i)ibeans[i]n - ikept014414312252103616The best target is 4, keeping 12 beans out of a totalof 16.total = sum(beans)kept = max(beans[i] * (n - i))answer = total - kept
After sorting, choosing beans[i] as the target means bags before i are emptied and bags from i onward are trimmed to beans[i].
ComplexityTime O(n log n)Space O(1) extraThe sort dominates; the single scan over the sorted array is linear, and only a few counters are stored.

What Trips People Up in Real Interviews

1

Assuming you must keep every bag non-empty. Emptying a bag completely is allowed and often optimal.

2

Trying every target value up to 10^5 without noticing only the bag sizes matter.

3

32-bit overflow on the total in C++/Java.

4

Forgetting to sort before using n - i as the count of bags at least as large.

Solution Code

O(n log n) time
def minimumRemoval(beans):
    beans.sort()
    n = len(beans)
    total = sum(beans)
    kept = max(b * (n - i) for i, b in enumerate(beans))
    return total - kept

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Removing Minimum Number of Magic Beans problem?

Removing Minimum Number of Magic Beans gives you bags of beans; you may remove beans so that every non-empty bag ends up with the same count. Minimize the number of beans removed. Sorting reveals the structure: pick a target equal to one of the bag sizes, empty the smaller bags, and trim the larger ones.

How do you solve Removing Minimum Number of Magic Beans?

The optimal approach runs in O(n log n) time and O(1) extra space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Removing Minimum Number of Magic Beans?

Removing Minimum Number of Magic Beans is asked at DE Shaw. It is a medium difficulty problem.

What are common mistakes on Removing Minimum Number of Magic Beans?
  • Assuming you must keep every bag non-empty. Emptying a bag completely is allowed and often optimal.
  • Trying every target value up to `10^5` without noticing only the bag sizes matter.
  • 32-bit overflow on the total in C++/Java.
  • Forgetting to sort before using `n - i` as the count of bags at least as large.