0894MediumArrayGreedySortingEnumerationPrefix Sum

Levelling the Seed Sacks

Tracked in this browser only

Trains the technique from

LeetCode 2171Removing Minimum Number of Magic Beans

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def minimum_removal(beans: list[int]) -> int:

Java

public long minimumRemoval(int[] beans)

The intended approach

Time O(n log n) for n sacks, the sort being the cost.Space O(n) for the sorted counts.

Whatever level the row ends at, that level must be the count of some sack, because raising the level as far as the next sack up keeps the same sacks in play while removing fewer seeds. So the answer is decided by which sack sets the level. Sort the counts. Fixing the level at the `i`-th smallest, every sack below it is emptied and every sack from it upward is cut back to that level, so the seeds kept are the level times the number of sacks from `i` onward, and the seeds removed are the row's total less that. Sweeping `i` over the sorted counts and keeping the smallest removal gives the answer in one pass.

Pythonentry point: minimum_removal

def minimum_removal(beans):
    order = sorted(beans)
    n = len(order)
    total = 0
    for v in order:
        total += v
    best = None
    for i in range(n):
        kept = order[i] * (n - i)
        removed = total - kept
        if best is None or removed < best:
            best = removed
    return best

The obvious version

Take every sack count in turn as the level the row will end at, then walk the whole row adding up what each sack would lose: everything, for a sack below the level, and the excess otherwise. Quadratic in the sack count and it never sorts or reasons about which levels are worth trying.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_removal(beans):
    best = None
    for level in beans:
        removed = 0
        for v in beans:
            if v < level:
                removed += v
            else:
                removed += v - level
        if best is None or removed < best:
            best = removed
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in