Show problems as
Classic problem #2171MediumArrayGreedySortingEnumerationPrefix Sum

Removing Minimum Number of Magic Beans

Real-world version: Levelling the Seed Sacks
Tracked in this browser only
Read Removing Minimum Number of Magic Beans on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A row of sacks holds seeds, beans[i] in sack i. Removing a seed takes it out of its sack for good.

The row is level when every sack that still holds any seeds holds the same number as every other such sack. A sack emptied completely does not count.

Return the fewest seeds that must be removed to leave the row level.

Examples

Example 1

Input
beans = [13, 4, 27, 4, 19]
Output
28

Levelling at 13 empties the two sacks of 4 and cuts 27 and 19 back, removing 4 plus 4 plus 14 plus 6, which is 28. Levelling at 19 removes 4, 4, 13 and 8, which is 29, and levelling at 4 removes 45, so 13 is the level to pick.

Example 2

Input
beans = [1, 100000]
Output
1

Emptying the sack of 1 leaves the big sack untouched, which costs a single seed. Cutting the big sack down to 1 would cost far more.

Example 3

Input
beans = [8, 8, 8, 8]
Output
0

The row is already level.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_removal(beans: list[int]) -> int:
Java
public long minimumRemoval(int[] beans)

More on the same topics