Loading...
Loading...
Loading...
At a village fair, children play a stone game. There are n stones, each with a whole-number weight.
Each turn, pick the two heaviest stones, with weights x ≥ y, and smash them together. If x equals y, both stones break and are gone. Otherwise the lighter stone is gone, and the heavier one now weighs x - y.
The game stops when at most one stone is left. Print the weight of the last stone, or 0 when no stone is left.
0.Example 1
Input
6 2 7 4 1 8 1
Output
1
8 and 7 leave 1. Then 4 and 2 leave 2. Then 2 and 1 leave 1. Then 1 and 1 both break, and the last stone weighs 1.
Example 2
Input
4 5 5 3 3
Output
0
The two 5s break, then the two 3s break. No stone is left.
Try the problem first. Open one hint at a time.
After every smash, the heaviest stones can change. Sorting once at the start is not enough.
You need a structure that always gives you the heaviest stone quickly, even after adding a new one.
Java keeps the smallest value on top of a PriorityQueue by default. Pass a comparator to keep the largest on top.
When a smash leaves a smaller stone, put it back into the same structure.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor