Last Stone Weight

Last Stone Weight is a problem in which we have a set of stones having some positive weights. Now we perform a task on it till we left 1 stone or no stone. We always pick two stones having the highest weight_value and smash them together. Let’s suppose the weight of stones is a,b, and a<=b. The result of the smash is:

• If a == b then both the stones are totally destroyed.
• If a !=b then the stone having weight=a is totally destroyed and the stone having weight=b has new weight b-a.

In the end, there is at most 1 stone left. Print the weight of this stone or if no stone left to print 0.

Input Format

First-line containing an integer value N describing the number of stones.

Second-line containing the weight of these stones such that w[i] denotes the weight of i-th stone.

Output Format

Print in a single line the weight of the left stone. If no stone left then print 0.

Constraints

• 1<=N<=10^5
• 1<=weight[i]<=10^9

6
2 7 4 1 8 1

1

Explanation

First, we pick two heaviest stones those are 7,8. Now we smash both of them and after smash stone with weight=1 is left. Now we again pick two heaviest stones in the set {2, 4, 1, 1, 1}. Here we got 2,4. Now after smashing them we left stone with weight=2. Again choose two heaviest stones from set {1, 1, 1, 2}. Here we got 1,2. Now smash them in and we got final stone with weight=1. Again we remain only 3 stones each of weight=1. Choose two stones from them and smash. Then both stones totally destroyed. Now we left only 1 stone then print the weight of that stone. Our left stone with weight=1 so we print 1.

Algorithm

Step:1 Push all the stones into priority_queue such that top of queue contain heaviest weight.
Step:2 While size of priority_queue is greater than 1 then:
             a) pop value from top of priority_queue and store in variable b.
             b) pop one more value and store in variable a.
             c) perform smash such that:
                    if a!=b then:
                      priority_queue.push_back(b-a).
Step:3 If size of priority queue is 0 then:
          Print 0.
       Else:
          Print size of the stone which is left in the priority_queue.

Implementation

/*C++ Implementation of Last Stone Weight.*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    /*input values.*/ 
    int n; 
    cin>>n;
    int weight[n];
    priority_queue<int> q;
    /*store elements in priority_queue*/
    for(int i=0;i<n;i++)
    {
        cin>>weight[i];
        q.push(weight[i]);
    }
    /*smash two heaviest stones till we reach the condition atmost 1 element present.*/
    while(q.size()>1)
    {
        /*heaviest stone.*/
        int a=q.top();
        q.pop();
        /*second heaviest stone.*/
        int b=q.top();
        q.pop();
        /*smash result*/
        if(a!=b)
        {
            q.push(a-b);
        }
    }
    /*print result*/
    if(q.empty())
    {
        cout<<0<<endl;
    }
    else
    {
        cout<<q.top()<<endl;
    }
    return 0; 
}

7
321 5 253 2 7 9 1045

448

Time Complexity

O(N*logN) where N is the number of stones given to us. We store the stones in priority queue which takes logN time to insert in the exact position of the element. Elements in the priority queue in increasing order. Means top of the stack is maximum and then second max second element from the top and so on…

Space Complexity

O(N) where N is the number of stones given to us. We use a priority queue which stores the element in increasing order.

References