Last Stone Weight

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 is:

• If x == y, both stones are totally destroyed;

• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

In the end, there is at most 1 stone left.  Find the weight of this stone.

Example:

Input:  stones[]={2,7,4,1,8,1}
Output: 1

Approach

Java

import java.util.PriorityQueue;

public class LastStoneWeight {
    public static void main(String[] args) {
        int stones[] = { 2, 7, 4, 1, 8, 1 };
        System.out.println(lastStoneWeight(stones));
    }

    // function to find the last stone weight
    private static int lastStoneWeight(int[] stones) {

        // make desc priority queue of all stones 
        PriorityQueue<Integer> q = new PriorityQueue<Integer>((x, y) -> y - x);
        for (int i = 0; i < stones.length; i++) {
            q.add(stones[i]);
        }

        // iterate till the priority queue size is
        // greater than 1
        while (q.size() > 1) {
            // pop top 2 elements
            int x = q.poll();
            int y = q.poll();

            // push the absolute value diff
            // of both the elements
            q.add(Math.abs(x - y));
        }
        // return the top of
        // priority queue
        return q.peek();
    }
    

}

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the last stone
//weight
int lastStoneWeight(vector<int>& stones) 
{

    //make priority queue of all stones
    priority_queue <int> q(stones.begin(), stones.end());

    //iterate till the priority queue size is
    //greater than 1
    while(q.size()>1)
    {

            //pop top 2 elements
            int x = q.top();
            q.pop();
            int y = q.top(); 
            q.pop();

            //push the absoulute value diff
            //of both the elements
            q.push(abs(x-y));
     }
  //return the top of
  //priority queue
   return q.top();
}
int main()
{
    vector<int> stones={2,7,4,1,8,1};
    cout<<lastStoneWeight(stones);
    return 0;

}