Show problems as
Classic problem #1962MediumArrayGreedyHeap (Priority Queue)

Remove Stones to Minimize the Total

Real-world version: Compactor Passes at the Scrap Yard
Tracked in this browser only
Read Remove Stones to Minimize the Total on LeetCode(opens in a new tab)

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

A scrap yard weighs the shredded metal sitting in each of its bins: bins[i] is the load of bin i in kilos. A booked slot on the yard's compactor gives the crew exactly passes passes, and every one of them has to be used.

A single pass is aimed at one bin of the crew's choosing. It takes away half of that bin's current load, rounded down, and leaves the rest in the bin. A bin holding one kilo therefore loses nothing when a pass is aimed at it, and the same bin may be chosen on as many passes as the crew likes.

Return the smallest total load, across all bins, that can be left in the yard once the booked passes have all been used.

Examples

Example 1

Input
bins = [12, 5], passes = 3
Output
6

The loads can be walked down to 3 and 3 by aiming two passes at the first bin and one at the second, leaving 6 kilos in the yard.

Example 2

Input
bins = [7, 7, 7], passes = 2
Output
15

Two of the bins drop from 7 to 4 kilos and the third is untouched, so 15 kilos remain.

Example 3

Input
bins = [26, 4, 18, 11], passes = 5
Output
22

One workable slot ends with loads 7, 4, 5 and 6, which add up to the figure returned.

Constraints

  • 1 <= bins.length <= 10^5
  • 1 <= bins[i] <= 10^4
  • 1 <= passes <= 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 least_scrap_left(bins: list[int], passes: int) -> int:
Java
public int leastScrapLeft(int[] bins, int passes)

More on the same topics