Removing Minimum Number of Magic Beans solution and explanation
7 more videos on this problem
Removing Minimum Number of Magic Beans | Leetcode 2171 | Contest 280 | TC O(nlogn) SC(1) 🔥🔥Coding Decoded · 9:54 · 2K views
2171. Removing Minimum Number of Magic Beans | LeetCode 2171 || LeetCode Weekly Contest 280Bro Coders · 11:37 · 2K views
2171. Removing Minimum Number of Magic Beans | LeetCode Solution | LeetCode | Weekly Contest 280viralSongs · 4:41 · 1K views
2171. Removing Minimum Number of Magic Beans (Leetcode Medium)Programming Live with Larry · 15:17 · 899 views
2171 Removing Minimum Number of Magic Beans | LeetCode 2171 | LeetCode Weekly Contest 280Vidit Shukla · 12:59 · 136 views
2171. Removing Minimum Number of Magic Beans Leetcode Medium PrefixSumRajat's corner ; Microsoft | IITG · 13:20 · 115 views
[LeetCode][Medium] 2171_Removing Minimum Number of Magic Beans 코드na982 · 2:17 · 67 views
2171. Removing Minimum Number of Magic BeansShuo Yan · 11:56 · 46 views
The 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 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 <= 1051 <= 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.
def minBeans(beans):
beans.sort()
total = sum(beans)
min_remove = total
for i, bean in enumerate(beans):
currentRemove = total - (len(beans) - i) * bean
if currentRemove < min_remove:
min_remove = currentRemove
return min_remove
# Example
beans = [4, 1, 6, 5]
print(minBeans(beans))import java.util.Arrays;
public class MinBeans {
public int minBeans(int[] beans) {
Arrays.sort(beans);
long total = 0;
for (int bean : beans) {
total += bean;
}
long minRemove = total;
for (int i = 0; i < beans.length; i++) {
long currentRemove = total - (long) (beans.length - i) * beans[i];
if (currentRemove < minRemove) {
minRemove = currentRemove;
}
}
return (int) minRemove;
}
public static void main(String[] args) {
MinBeans solver = new MinBeans();
int[] beans = {4, 1, 6, 5};
System.out.println(solver.minBeans(beans));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minBeans(std::vector<int>& beans) {
std::sort(beans.begin(), beans.end());
long long total = 0;
for (int bean : beans) {
total += bean;
}
long long minRemove = total;
for (size_t i = 0; i < beans.size(); ++i) {
long long currentRemove = total - (static_cast<long long>(beans.size() - i) * beans[i]);
if (currentRemove < minRemove) {
minRemove = currentRemove;
}
}
return static_cast<int>(minRemove);
}
int main() {
std::vector<int> beans = {4, 1, 6, 5};
std::cout << minBeans(beans) << std::endl;
return 0;
}function minBeans(beans) {
beans.sort((a, b) => a - b);
let total = beans.reduce((acc, val) => acc + val, 0);
let minRemove = total;
for (let i = 0; i < beans.length; i++) {
let currentRemove = total - (beans.length - i) * beans[i];
minRemove = Math.min(minRemove, currentRemove);
}
return minRemove;
}
// Example
let beans = [4, 1, 6, 5];
console.log(minBeans(beans));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minBeans(int* beans, int beansSize) {
qsort(beans, beansSize, sizeof(int), compare);
int total = 0;
for (int i = 0; i < beansSize; i++) {
total += beans[i];
}
int minRemove = total;
int currSum = 0;
for (int i = 0; i < beansSize; i++) {
int currentRemove = total - (beansSize - i) * beans[i];
if (currentRemove < minRemove) {
minRemove = currentRemove;
}
currSum += beans[i];
}
return minRemove;
}
int main() {
int beans[] = {4, 1, 6, 5};
int beansSize = sizeof(beans) / sizeof(beans[0]);
int result = minBeans(beans, beansSize);
printf("%d\n", result);
return 0;
}using System;
class MinBeans {
public int MinBeansMethod(int[] beans) {
Array.Sort(beans);
long total = 0;
foreach (int bean in beans) {
total += bean;
}
long minRemove = total;
for (int i = 0; i < beans.Length; i++) {
long currentRemove = total - ((long) (beans.Length - i) * beans[i]);
if (currentRemove < minRemove) {
minRemove = currentRemove;
}
}
return (int) minRemove;
}
static void Main() {
MinBeans solver = new MinBeans();
int[] beans = {4, 1, 6, 5};
Console.WriteLine(solver.MinBeansMethod(beans));
}
}This solution leverages Python's built-in sort to arrange the beans and calculates the minimal number of beans that should be removed by iterating over the sorted list.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) because no additional space beyond input storage is used.
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.
def beansToRemove(beans, target):
removed = 0
for bean in beans:
if bean < target:
removed += bean
else:
removed += target
return removed
def minBeans(beans):
beans.sort()
result = float('inf')
for target in beans:
currentRemove = beansToRemove(beans, target)
result = min(result, currentRemove)
return result
# Example
beans = [4, 1, 6, 5]
print(minBeans(beans))import java.util.Arrays;
public class MinBeans {
private int beansToRemove(int[] beans, int target) {
int removed = 0;
for (int bean : beans) {
if (bean < target) {
removed += bean;
} else {
removed += target;
}
}
return removed;
}
public int minBeans(int[] beans) {
Arrays.sort(beans);
int result = Integer.MAX_VALUE;
for (int bean : beans) {
int currentRemove = beansToRemove(beans, bean);
result = Math.min(result, currentRemove);
}
return result;
}
public static void main(String[] args) {
MinBeans solver = new MinBeans();
int[] beans = {4, 1, 6, 5};
System.out.println(solver.minBeans(beans));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int beansToRemove(const std::vector<int>& beans, int target) {
int removed = 0;
for (int i = 0; i < beans.size(); ++i) {
if (beans[i] < target) {
removed += beans[i];
} else {
removed += target;
}
}
return removed;
}
int minBeans(std::vector<int>& beans) {
std::sort(beans.begin(), beans.end());
int result = INT_MAX;
for (int target : beans) {
int currentRemove = beansToRemove(beans, target);
result = std::min(result, currentRemove);
}
return result;
}
int main() {
std::vector<int> beans = {4, 1, 6, 5};
std::cout << minBeans(beans) << std::endl;
return 0;
}function beansToRemove(beans, target) {
let removed = 0;
for (let bean of beans) {
if (bean < target) {
removed += bean;
} else {
removed += target;
}
}
return removed;
}
function minBeans(beans) {
beans.sort((a, b) => a - b);
let result = Infinity;
for (let target of beans) {
let currentRemove = beansToRemove(beans, target);
result = Math.min(result, currentRemove);
}
return result;
}
// Example
let beans = [4, 1, 6, 5];
console.log(minBeans(beans));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int beansToRemove(int* beans, int beansSize, int target) {
int removed = 0;
int i = 0;
while (i < beansSize && beans[i] < target) {
removed += beans[i];
i++;
}
removed += (beansSize - i) * target;
return removed;
}
int minBeans(int* beans, int beansSize) {
qsort(beans, beansSize, sizeof(int), compare);
int left = 0, right = beans[beansSize - 1];
int result = INT_MAX;
for (int i = 0; i < beansSize; ++i) {
int currentRemove = beansToRemove(beans, beansSize, beans[i]);
if (currentRemove < result) {
result = currentRemove;
}
}
return result;
}
int main() {
int beans[] = {4, 1, 6, 5};
int beansSize = sizeof(beans) / sizeof(beans[0]);
int result = minBeans(beans, beansSize);
printf("%d\n", result);
return 0;
}using System;
class MinBeans {
public int BeansToRemove(int[] beans, int target) {
int removed = 0;
foreach (int bean in beans) {
if (bean < target) {
removed += bean;
} else {
removed += target;
}
}
return removed;
}
public int MinBeansMethod(int[] beans) {
Array.Sort(beans);
int result = int.MaxValue;
foreach (int bean in beans) {
int currentRemove = BeansToRemove(beans, bean);
result = Math.Min(result, currentRemove);
}
return result;
}
static void Main() {
MinBeans solver = new MinBeans();
int[] beans = {4, 1, 6, 5};
Console.WriteLine(solver.MinBeansMethod(beans));
}
}By iterating over each unique bean value as a prospective uniform value, this implementation checks and stores minimal bean removals, tackling each candidate efficiently.
Time Complexity: O(n log n + n), necessitated by sorting and iterations.
Space Complexity: O(1).
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.
function minimumRemoval(beans: number[]): number {
beans.sort((a, b) => a - b);
const s = beans.reduce((a, b) => a + b, 0);
const n = beans.length;
let ans = s;
for (let i = 0; i < n; ++i) {
ans = Math.min(ans, s - beans[i] * (n - i));
}
return ans;
}func minimumRemoval(beans []int) int64 {
sort.Ints(beans)
s := 0
for _, x := range beans {
s += x
}
ans := s
n := len(beans)
for i, x := range beans {
ans = min(ans, s-x*(n-i))
}
return int64(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Prefix Sum Method | Time Complexity: O(n log n) for sorting. |
| Binary Search and Counting | Time Complexity: O(n log n + n), necessitated by sorting and iterations. |
| Sorting + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Prefix Sum | O(n log n) | O(n) | Best general solution. Efficiently evaluates each possible target bean count. |
| Binary Search and Counting | O(n log n) | O(1)–O(n) | Useful when explicitly finding boundaries of bags to remove using binary search. |
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.