Loading problem...
You are given an array of positive integers representing the masses of various objects. You are participating in a collision experiment where, in each turn, you may select any two objects and collide them together.
When two objects with masses x and y collide (where x ≤ y), the following outcomes occur:
x == y, both objects are completely annihilated and no residue remains.x != y, the lighter object is destroyed, and the heavier object is reduced to a new object with mass y - x.The experiment continues until at most one object remains.
Your goal is to determine the minimum possible mass of the final remaining object after optimally performing all collisions. If all objects can be completely annihilated, return 0.
Key Insight: The order and choice of collisions matter significantly in achieving the minimum final mass. This problem is fundamentally about partitioning the objects into two groups such that the absolute difference of their total masses is minimized.
stones = [2,7,4,1,8,1]1One optimal sequence of collisions: • Collide 4 and 2 → residue 2, array becomes [2,7,1,8,1] • Collide 8 and 7 → residue 1, array becomes [2,1,1,1] • Collide 2 and 1 → residue 1, array becomes [1,1,1] • Collide 1 and 1 → both annihilated, array becomes [1] The minimum possible residue is 1.
stones = [31,26,33,21,40]5The total mass is 151. By optimally partitioning into two groups: {40, 33} = 73 and {31, 26, 21} = 78, the difference is |78 - 73| = 5. This is the minimum achievable residue.
stones = [1,2,3]0One approach: collide 1 and 2 to get 1, then collide that 1 with 3 to get 2, then... Actually, a better approach: collide 1 and 3 to get 2, then collide the two 2s to completely annihilate. Or equivalently, partition into {1, 2} = 3 and {3} = 3, difference = 0.
Constraints