Last Stone Weight II in C++

Suppose we have a collection of rocks, now each rock has a positive integer weight. In each turn, we choose any two rocks and smash them together. If the stones have weights x and y with x <= y. The result of this smash will be −

• 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.

Finally, there is at most 1 stone left. We have to find the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

So for example, if the input is like [2,7,4,1,8,1], then the output will be 1. This is because if we smash (2,4), then the new array will be [2,7,1,8,1], them smash (7,8), the new array will be [2,1,1,1], then smash (2,1), the array will be [1,1,1], after that smash (1,1), so only 1 will be there.

To solve this, we will follow these steps −

• n := size of the stones array, set total := 0

• for i in range 0 to n – 1

  • total := total + stones[i]

• req := total / 2

• make an array dp of size req + 1, and fill this with false values

• dp[0] := true, reach := 0

• for i in range 0 to n – 1

  • for j := req, when j – stones[i] >= 0, decrease j by 1

    • dp[j] := false when (dp[j] and dp[j – stones[i]]) both are false, otherwise true

    • if dp[j] is true, then reach := max of reach and j

• return total – (2 * reach)

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int lastStoneWeightII(vector<int>& stones) {       int n = stones.size();       int total = 0;       for(int i = 0; i < n; i++){          total += stones[i];       }       int req = total / 2;       vector <bool> dp(req + 1, false);       dp[0] = true;       int reach = 0;       for(int i = 0; i < n; i++){          for(int j = req; j - stones[i] >= 0; j--){             dp[j] = dp[j] || dp[j - stones[i]];             if(dp[j]) reach = max(reach, j);          }       }       return total - (2 * reach);    } }; main(){    vector<int> v = {2,7,4,1,8,1};    Solution ob;    cout << (ob.lastStoneWeightII(v)); }

Input

[2,7,4,1,8,1]

Output

1