What is the key pattern in Removing Minimum Number of Magic Beans?

The problem follows a greedy choice plus invariant validation pattern, where smallest bags are emptied first to maintain equality.

How do I decide which bags to empty first?

Always start with the bags containing the fewest beans, as emptying them first minimizes total removals while keeping the remaining bags equal.

Can prefix sums speed up the solution?

Yes, prefix sums allow efficient calculation of total beans removed from bags before and after each target position, improving O(n) computation after sorting.

Does the solution work for large arrays up to 10^5 elements?

Yes, sorting and prefix sum computation scales efficiently, meeting constraints of 1 <= beans.length <= 105.

Is it ever optimal to leave more than one smallest bag non-empty?

No, keeping multiple smallest bags increases total removals; the greedy invariant ensures minimal removal by emptying the smallest bags first.

#2171

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

拿出最少数目的魔法豆

给定一个正整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出一些豆子（也可以不拿出），使得剩下的非空袋子中（即至少还有一颗魔法豆的袋子）魔法豆的数目相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。请返回你需要拿出魔法豆的 …

数组贪心排序枚举前缀和

题目描述

给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中拿出一些豆子（也可以 不拿出），使得剩下的非空袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的 最少数目。

示例 1：

输入：beans = [4,1,6,5]
输出：4
解释：
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

示例 2：

输入：beans = [2,10,3,2]
输出：7
解释：
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。

提示：

1 <= beans.length <= 10⁵
1 <= beans[i] <= 10⁵

lightbulb

解题思路

方法一：排序 + 枚举

我们可以将所有袋子中的魔法豆按照从小到大的顺序排列，然后枚举每个袋子的魔法豆数目 $beans[i]$ 作为最终袋子中魔法豆数目，那么一共剩余的魔法豆数目为 $beans[i] \times (n - i)$ ，因此需要拿出的魔法豆数目为 $s - beans[i] \times (n - i)$ ，其中 $s$ 为所有袋子中魔法豆的总数。我们求出所有方案中需要拿出的魔法豆数目的最小值即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为袋子的数目。

1

2

3

4

5

6

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        s, n = sum(beans), len(beans)
        return min(s - x * (n - i) for i, x in enumerate(beans))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a strategy that reduces the problem to a sorted array and considers each unique bean count as a target.
question_mark
Ask candidates how removing the smallest bags first maintains the invariant for remaining equal bags.
question_mark
Check if the candidate considers cumulative sums or prefix sums to compute removals efficiently.

warning

常见陷阱

外企场景

error
Failing to sort the array before applying the greedy choice leads to incorrect minimal removal calculation.
error
Removing beans without considering the invariant that remaining bags must all have equal beans.
error
Overcomplicating by trying to adjust bags in arbitrary order instead of emptying smallest bags first.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to maximize remaining beans instead of minimizing removals using the same greedy invariant approach.
arrow_right_alt
Consider cases where only a subset of bags must match a target, requiring selective greedy removal.
arrow_right_alt
Introduce multiple bean types per bag and require equality per type, extending the prefix sum and greedy logic.

help

常见问题

外企场景

继续练习

#2234 花园的最大总美丽值 #2271 毯子覆盖的最多白色砖块数 #2389 和有限的最长子序列