Ctrl K

Shrink the Tallest Pile

Easy
There are piles of coins on a table, piles[i] being the number of coins in pile i. The game lasts rounds rounds. In each round you pick the tallest pile (any of them if there is a tie) and take coins from it so that ⌊√x⌋ remain, where x is how many it had. Return the total number of coins left on the table across all piles after the last round.
Example 1
piles=[50, 10, 3], rounds=3 → 8

First 50 → 7, then the tallest pile is 10 → 3, then 7 → 2. That leaves 2 + 3 + 3 = 8.

Example 2
piles=[100], rounds=5 → 1

100 → 10 → 3 → 1, and after that a pile of one coin no longer shrinks.

Constraints
  • 1 ≤ len(piles) ≤ 10⁵
  • 1 ≤ piles[i] ≤ 10⁹
  • 1 ≤ rounds ≤ 10⁵
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsClearing the Stacks Evenly EasyPeel Off the Row Maximums EasyMasha and Pete Stack the Cards EasyBoost the Smallest EasyShuttle Seat Plan Medium
loading Python…
Input
piles=[50, 10, 3], rounds=3
Expected
8

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.