removing-minimum-number-of-magic-beans

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of positive integers <code>beans</code>, 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.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= beans.length &lt;= 105</code></li>
	<li><code>1 &lt;= beans[i] &lt;= 105</code></li>
</ul>

minimumRemoval

Removing Minimum Number of Magic Beans

Minimum Moves to Equal Array Elements II

minimum-moves-to-equal-array-elements-ii

最小操作次数使数组元素相等 II

Minimum Operations to Reduce X to Zero

minimum-operations-to-reduce-x-to-zero

将 x 减到 0 的最小操作数

Greedy

Array

Enumeration

Prefix Sum

Sorting

给定一个 正整数&nbsp;数组&nbsp;<code>beans</code>&nbsp;，其中每个整数表示一个袋子里装的魔法豆的数目。

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

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

&nbsp;

示例 1：

<pre>
输入：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 个魔法豆更少的方案。
</pre>

示例 2：

<pre>
输入：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 个魔法豆更少的方案。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= beans.length &lt;= 105</code></li>
	<li><code>1 &lt;= beans[i] &lt;= 105</code></li>
</ul>