CodePark/ problems / Smash the Heaviest Stones
START PRACTICINGPRACTICE
Coding problem · Data structures and algorithms › Heaps and top-k

Smash the Heaviest Stones

easyabout 15 minutes in an interview

stones lists the weights of some stones. Each weight is a positive whole number. Repeat these steps:

  1. Pick the two heaviest stones. Call the lighter weight x and the heavier one y, so x <= y.
  2. If x === y, remove both.
  3. If not, remove both and put back one stone that weighs y - x.

Stop when one stone or none is left. Return the weight of the stone that is left, or 0 if none is.

  • stones holds between 1 and 1,000 stones.
  • Each weight is between 1 and 1,000.
  • stones may be in any order.
Input: stones = [6, 4, 9, 2] Output: 19 and 6 leave 3. Then 4 and 3 leave 1. Then 2 and 1 leave 1. One stone of weight 1 is left.
Input: stones = [3, 3] Output: 0
Input: stones = [7] Output: 7