Last Updated: 17 Jul, 2020
Last Stone Weight
Easy
Asked in companies
We have a collection of 'N' stones, each stone has a positive integer weight.
On each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights 'x' and 'y' with 'x' <= 'y'. The result of this smash will be:
1. If 'x' == 'y', both stones are totally destroyed;
2. If 'x' != 'y', the stone of weight 'x' is totally destroyed, and the stone of weight 'y' has a new weight equal to 'y - x'.
In the end, there is at most 1 stone left. Return the weight of this stone or 0 if there are no stones left.
Input format:
The first line of input contains the integer 'N', representing the total number of stones.
The second line of input contains 'N' single space-separated integers, representing the weights of the stones.
Output Format:
The only output line prints the weight of the last stone, if it exists, 0 otherwise.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints :
1 <= N <= 10^5
1 <= W <= 10^6
Time Limit: 1 sec
Approaches
We will store the stones in a vector/list and run a while loop until the size of the vector/list is greater than 1
- Find the index and weight of the two heaviest stones
- Remove those stones from the vector/list using their index
- Add their absolute difference to the vector/list if the absolute difference is greater than 0
We can use a max priority queue to solve this question. Store the weights of all stones in the queue and then while its size is greater than 1 do the following:
- Pop two elements from the queue. These will be the two largest elements in the queue.
- Then, find the positive difference between the two popped elements and if it's greater than zero, insert it into the queue.
After you've completed the above process, you should have one element left in the queue. Simply return it.
Similar problems