Problem 60256. Final Stone Weight

minnolina

14 solvers

1 likes

Solve

Solve Later

You are given an array with weights of stones. The objective is to determine the weight of the final stone remaining after all collisions have occurred. If there are no stones left, the result is 0.
Here's how the process works:
Remove the two heaviest stones from the array.
Collide these two stones together, which results in a new stone. The weight of this new stone is the difference between the weights of the two original stones.
Add the new stone back into the array. After this step, the initial array has one less element.
Repeat the process until only one or no stone remains.
Example:
Consider an initial array of stones with weights [9, 15, 20, 25, 30]
First, take the heaviest stones, 30 and 25. The collision results in a new stone of weight 30-25=5. The updated array of stones is now: [9, 15, 20, 5]
Next, take the heaviest stones, 20 and 15. The collision results in a new stone of weight 20-15=5. The updated array of stones is now: [9, 5, 5]
Then, take the heaviest stones, 9 and 5. The collision results in a new stone of weight 9-5=4. The updated array of stones is now: [4, 5]
Finally, take the heaviest stones, 5 and 4. The collision results in a new stone of weight 5-4=1. The updated array of stones is now: [1]
So, the weight of the final stone is 1.
                    
       