Boulder Crusher
EasyHeap / Priority QueueFree
Problem
A quarry crusher works on a pile of boulders with integer weights. Each round it takes the two heaviest boulders, a ≥ b, and smashes them together: if a == b both turn to dust; otherwise the lighter one turns to dust and the heavier one survives with weight a - b, going back onto the pile.
The crusher stops when at most one boulder is left. Return the weight of that boulder, or 0 if nothing is left.
Example 1
- Input:
- weights = [6, 2, 9, 3]
- Output:
- 2
9 and 6 → 3; pile [2, 3, 3]. 3 and 3 → dust; pile [2]. One boulder of weight 2 remains.
Example 2
- Input:
- weights = [4, 4]
- Output:
- 0
Example 3
- Input:
- weights = [10]
- Output:
- 10
Constraints
- 1 ≤ weights.length ≤ 10^4
- 1 ≤ weights[i] ≤ 10^4
Hint
Show the first hint
Every round needs the two largest values of a collection that keeps changing.
Walkthrough
How to approach it
01Clarify before coding
- What if the two heaviest are equal? Both disappear and nothing is pushed back.
- What if only one boulder exists from the start? Return its weight; no round happens.
- Can weights be zero? No, all start positive, and a zero difference is never pushed back.
02Brute force
Each round, sort the pile, take the last two, and append the difference if non-zero.
Cost: O(n² log n) time: up to n rounds, each sorting up to n values. For n = 10^4 that is far too much work for two numbers per round.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.