You have an array stones of positive integer weights. On each turn you choose any two stones with weights x ≤ y and smash them together: if x === y both are destroyed, otherwise the stone of weight x is destroyed and the other becomes weight y − x. After at most n − 1 turns at most one stone remains. Return the smallest possible weight of the remaining stone, or 0 if none remains.
- You choose which two stones to smash, so this is not the "two heaviest" heap problem
- Think of the stones as being split into two groups; what is the last weight in terms of the groups?
- Target complexity: O(n · sum) time, O(sum) space