Skip to main content
Talentd

Removing Minimum Number of Magic Beans - Solution & Explanation

MediumArrayGreedySortingEnumeration19 min readAsked at: De Shaw
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array where beans[i] represents the number of magic beans in the i-th bag. Remove the minimum number of beans so that every non-empty bag ends up with the same number of beans. Bags can become empty after removals.

Approach 1: Sorting and Prefix Sum Method (O(n log n) time, O(n) space)

The key observation: if the final number of beans per non-empty bag is x, every bag with fewer than x beans must be emptied completely, while bags with more than x beans must be reduced down to x. Start by sorting the array so potential target values appear in increasing order. Build a prefix sum to quickly compute how many beans exist in any prefix. When you choose beans[i] as the target value, all bags before i are removed entirely and all bags after i are trimmed down to beans[i]. The number of beans kept becomes beans[i] * (n - i), so the removed beans equal totalSum - kept. Iterate through all indices and track the minimum removal. This approach relies on sorting and prefix sum to evaluate each candidate efficiently.

Approach 2: Binary Search and Counting (O(n log n) time, O(1)–O(n) space)

Another way to think about the problem is to enumerate possible target bean counts and quickly determine how many bags must be removed or trimmed. After sorting the array, use binary search to locate the first position where the bag count is at least the target value. All earlier bags are emptied. For bags on the right, count how many exceed the target and subtract the excess. This method treats each candidate value as a decision point and uses binary search to find boundaries efficiently. It still relies on sorted order and works well when you want explicit counting logic rather than computing totals directly. The strategy combines array processing with a greedy observation that only existing bag sizes need to be considered as targets.

Recommended for interviews: The sorting + prefix sum solution is the expected approach. Interviewers want to see the greedy insight that the final value must match one of the existing bag sizes and that sorting lets you evaluate each candidate efficiently. A brute-force idea (trying every possible bean count) shows understanding of the constraint, but the prefix-sum optimization demonstrates strong algorithmic reasoning.

Approach 1: Sorting and Prefix Sum Method

The idea is to sort the array and try to make the content of each bag equal to the number of beans in every successive bag. By considering each unique value in the sorted array as a candidate to make all bags equal, we can calculate and minimize the number of beans to be removed using prefix sum. This is efficient because after sorting, all the candidates to make bags equal are in a sequence, which reduces the solution complexity.

The solution sorts the array and computes the total number of beans. Then, using a loop, it calculates the minimum beans that need to be removed by evaluating each unique value in the sorted array as the desired number of beans per bag.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is done in place and only constant extra space is used.

Try this approach in the editor →

Approach 2: Binary Search and Counting

This approach involves using binary search to find the optimal value that can be set as the target for all bags. We perform counting to compute how many beans need to be removed if we choose each bean value as the target. This can allow for a more refined search over possible values without needing to sequentially check each potential number like in the previous approach.

This solution uses binary search through possible target values for beans. For each possible target, it calculates how many beans need to be removed and minimizes this number across potential targets.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log m + m), for sorting and evaluating each target across a range.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Sorting + Enumeration

We can sort all the beans in the bags in ascending order, and then enumerate the number of beans beans[i] in each bag as the final number of beans in the bag. The total remaining number of beans is beans[i] times (n - i), so the number of beans that need to be taken out is s - beans[i] times (n - i), where s is the total number of beans in all bags. We need to find the minimum number of beans that need to be taken out among all schemes.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of bags.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Prefix Sum Method

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the sorting is done in place and only constant extra space is used.

Binary Search and Counting

Time Complexity: O(n log m + m), for sorting and evaluating each target across a range.
Space Complexity: O(1).

Sorting + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Prefix SumO(n log n)O(n)Best general solution. Efficiently evaluates each possible target bean count.
Binary Search and CountingO(n log n)O(1)–O(n)Useful when explicitly finding boundaries of bags to remove using binary search.

Video Solution

Removing Minimum Number of Magic Beans | Leetcode 2171 | Contest 280 | TC O(nlogn) SC(1) 🔥🔥 • Coding Decoded • 2,374 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Removing Minimum Number of Magic Beans easy or hard?
Removing Minimum Number of Magic Beans is classified as Medium difficulty. The challenge is recognizing the greedy insight that the final equal value must match an existing bag size and then efficiently evaluating each candidate using sorting and prefix sums.
Removing Minimum Number of Magic Beans Python/Java solution
In Python or Java, sort the array and compute the total number of beans. For each index i, assume beans[i] is the final count per bag and calculate beans[i] * (n - i) as the number of beans kept. Subtract this from the total to get removed beans, and track the minimum across all indices.
How to solve Removing Minimum Number of Magic Beans in O(n)?
Pure O(n) time is generally not achievable because determining the optimal target value requires considering bag sizes in sorted order. The closest optimal approach is O(n log n) using sorting followed by a linear pass. During that pass, compute how many beans remain if all larger bags are reduced to the current value.
What is the best approach for Removing Minimum Number of Magic Beans?
The most efficient approach is sorting combined with a greedy observation and prefix sums. After sorting the bags, treat each bean count as the potential final value for all non-empty bags. Compute how many beans remain if every bag from that index onward is reduced to that value. The minimum removal can be found in O(n log n) time due to sorting.
Is Removing Minimum Number of Magic Beans asked at Google/Amazon/Meta?
Problems combining greedy reasoning with sorting and prefix sums appear frequently in interviews at companies like Amazon, Google, and Meta. Variations that ask you to equalize values by removing elements or minimizing operations are common in mid-level algorithm interviews.
What data structure is used in Removing Minimum Number of Magic Beans?
The solution primarily uses arrays along with sorting and prefix sum calculations. Sorting allows evaluation of candidate target values efficiently, while prefix sums or total-sum arithmetic help compute how many beans remain or must be removed in constant time per iteration.
What is the time complexity of Removing Minimum Number of Magic Beans?
The optimal solution runs in O(n log n) time because the array must be sorted. After sorting, a single linear scan evaluates each candidate value using prefix sums or total sum arithmetic. Space complexity is typically O(n) for prefix sums or O(1) if only totals are tracked.

Ready to solve this problem?

Practice Removing Minimum Number of Magic Beans with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Moves to Equal Array Elements II

Next

Minimum Operations to Reduce X to Zero