Last Stone Weight II

The key idea

Give every stone a + or - sign and smash everything together at once. The final weight is the absolute value of the signed sum, so you want to split the stones into two piles whose sums are as close as possible. With total S, find the largest reachable subset sum p that is at most S/2; the answer is S - 2*p.

Problem

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

On each turn you choose any two stones and smash them together. Suppose the two stones have weights x and y with x <= y. The result of the smash is:

- If x == y, both stones are destroyed.
- If x != y, the stone of weight x is destroyed and the stone of weight y becomes y - x.

At the end of the game there is at most one stone left. Return the smallest possible weight of that last remaining stone. If no stones are left, return 0.

Constraints

1 <= stones.length <= 30
1 <= stones[i] <= 100

Examples

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

Input: stones = [31,26,33,21,40] Output: 5

Complexity

Time: O(n * S) Space: O(S)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →