0716MediumArrayDynamic ProgrammingKnapsack Problem0-1 Knapsack

Trimming The Bar Rack Down

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def smallest_last_bar(bars: list[int]) -> int:

Java

public int smallestLastBar(int[] bars)

The intended approach

Time O(n * total) for n bars of combined length total: each bar widens the set of assembled group lengths, which never exceeds total + 1 entries.Space O(total) for the set of assembled group lengths.

Follow one bar's contribution through the trimming: whatever order the pairs are fed in, each original bar finishes counted once, either in the same direction as the surviving bar or against it, so the last length is the size of the difference between the two groups. Writing the combined length as `total`, a group of length `value` leaves `|total - 2 * value|`, so the task is to find which group lengths can be assembled from the rack. Start from the single group length 0 and, for each bar in turn, add that bar's length to every group length already assembled, which keeps each bar usable once. The answer is the assembled group length whose doubled value lands closest to the combined length.

Pythonentry point: smallest_last_bar

def smallest_last_bar(bars):
    # Every bar ends up either added to or subtracted from the running length, so the
    # final bar is |total - 2 * (length put on one side)|.  Collect exactly the side
    # totals that can be assembled from the rack, one bar at a time, and keep the
    # side total that lands closest to half the rack.
    # Time O(n * total) for n bars of combined length total; space O(total).
    total = sum(bars)
    reachable = {0}
    for length in bars:
        reachable |= {value + length for value in reachable}
    best = total
    for value in reachable:
        gap = total - 2 * value
        if gap < 0:
            gap = -gap
        if gap < best:
            best = gap
    return best

The obvious version

Search the trimming itself: from a rack, try every pair that could be fed through, recurse on the rack that results, and keep the smallest finish, remembering each rack already solved. Exponential in the number of bars, so it only runs on a small rack, but it assumes nothing at all about groups or differences.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_smallest_last_bar(bars):
    memo = {}

    def solve(rack):
        if len(rack) <= 1:
            return rack[0] if rack else 0
        if rack in memo:
            return memo[rack]
        best = None
        for i in range(len(rack)):
            for j in range(i + 1, len(rack)):
                rest = list(rack[:i]) + list(rack[i + 1:j]) + list(rack[j + 1:])
                made = rack[j] - rack[i]
                if made:
                    rest.append(made)
                value = solve(tuple(sorted(rest)))
                if best is None or value < best:
                    best = value
        memo[rack] = best
        return best

    return solve(tuple(sorted(bars)))

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in