Last Stone Weight II
Real-world version: Trimming The Bar Rack DownThe statement here is our own: the same inputs, outputs and technique.
A fabrication shop keeps a rack of steel bars, and bars[i] is the length of one of them.
While at least two bars sit on the rack, the operator takes any two of them and feeds the pair through the trimmer. Both bars are consumed. If the two lengths are different, a single bar comes out whose length is the difference between them, and it goes back on the rack. If the two lengths are equal, nothing comes out.
The operator keeps trimming until fewer than two bars are left, so the rack finishes with either one bar or none. The operator chooses which pair to feed through at every step.
Return the smallest length the last bar can have, or 0 if the rack can be left empty.
Examples
Example 1
- Input
- bars = [5, 3, 6]
- Output
- 2
Feed the 6 and the 5 through together and a bar of length 1 comes out, leaving lengths 3 and 1 on the rack. Feeding those two through leaves one bar of length 2.
Example 2
- Input
- bars = [4, 4]
- Output
- 0
The two bars are the same length, so feeding the pair through consumes both and nothing comes out. The rack is left empty.
Example 3
- Input
- bars = [12, 9, 3]
- Output
- 0
Feed the 12 and the 9 through together and a bar of length 3 comes out, so the rack holds 3 and 3. Feeding that pair through consumes both and leaves the rack empty.
Constraints
- 1 <= bars.length <= 30
- 1 <= bars[i] <= 100
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def smallest_last_bar(bars: list[int]) -> int:public int smallestLastBar(int[] bars)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 18 test cases: 18 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's