easyHeap / Priority QueuePure DSA~13 min
Batch Merge Largest Two
A compaction job repeatedly takes the two largest pending batch sizes and merges them: equal sizes cancel out, otherwise the difference remains. Find the final leftover size.
Problem
Given an array of positive integers stones, repeatedly remove the two largest values x ≥ y. If x == y both are destroyed; otherwise a new stone of value x − y is added. Return the value of the last remaining stone, or 0 if none remain.
Input
An array stones of length n (1 ≤ n ≤ 30), values in [1, 1000].
Output
An integer — the last remaining value, or 0.
Constraints
- Always operate on the two current largest values
- Equal pairs annihilate
- Result is 0 when all stones cancel
Examples
Example 1
Input
stones = [2, 7, 4, 1, 8, 1]
Output
1
8,7→1; then 4,2→2; 2,1,1,1 → … finishes at 1.
Example 2
Input
stones = [1, 1]
Output
0
Equal pair annihilates, nothing remains.