The Final Stone

The Final Stone

You have a list of stones with different weights. The result of hitting two stones will be a new stone with a weight difference between the two stones.

example

Your goal is to find the weight of the final stone. If no stones left, the result is 0.

The algorith is very simple:

  • get the two biggest stones in the batch
  • hit and get the resulting stone
  • put the resulting stone back in the batch.

For the Speedy category, you can think about your solution for a million stones

Input: List of stones as list of ints

Output: Int.

Example:

assert final_stone([3, 5, 1, 1, 9]) == 1
assert final_stone([1, 2, 3]) == 0
assert final_stone([1, 2, 3, 4]) == 0
assert final_stone([1, 2, 3, 4, 5]) == 1

Precondition: only positive, non-zero values. The list of stones can be empty

40