0359HardArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Settle the Makerspace Books

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 shared makerspace keeps a log of who covered whose costs. Every element of transactions is a triple [a, b, amount], meaning member a put up amount credits towards a bill that belonged to member b. Member b is therefore short that many credits and member a is ahead by the same.

At the end of the term the books are closed. The log fixes every member's net position: a member is up by the credits they fronted for others and down by the credits others fronted for them. To close the books, credits are moved one transfer at a time. A transfer sends any amount you like from one member to another and does not have to mirror a log entry.

Return the smallest number of transfers that leaves every member with a net position of zero. Members whose position is already zero need no transfer at all.

Examples

Example 1

Input: transactions = [[0,1,20],[2,1,5]]
Output: 2

Member 0 is up 20, member 2 is up 5 and member 1 is down 25. Two transfers zero everyone: member 1 sends 20 to member 0 and 5 to member 2.

Example 2

Input: transactions = [[0,1,15],[1,2,15]]
Output: 1

Member 1 fronted 15 and had 15 fronted for them, so their position is already zero. One transfer of 15 credits from member 2 to member 0 closes the books.

Example 3

Input: transactions = [[1,6,7],[3,0,5],[4,0,4],[2,6,10]]
Output: 4

Positions are +7 for member 1, +10 for member 2, +5 for member 3, +4 for member 4, -9 for member 0 and -17 for member 6. Four transfers zero them all: member 6 sends 7 to member 1 and 10 to member 2, and member 0 sends 5 to member 3 and 4 to member 4.

Example 4

Input: transactions = [[0,1,10],[1,0,10]]
Output: 0

The two entries cancel, so both members finish at zero and nothing needs to move.

Constraints

1 <= transactions.length <= 8
transactions[i].length == 3
0 <= a, b < 12
a != b
1 <= amount <= 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 min_transfers(transactions: list[list[int]]) -> int:

Java

public int minTransfers(int[][] transactions)

The intended approach

Time O(2^m * m) where m <= 12 is the number of members with a non-zero net positionSpace O(2^m) for the subset sum and block count tables

Collapse the log into one net position per member and drop the members already at zero, leaving m <= 12 numbers that sum to zero. A block of members whose positions sum to zero can be cleared with one fewer transfer than it has members, so splitting the m numbers into as many zero-sum blocks as possible minimises the total. A subset table holds the sum of every mask, and a second table takes the best block count of every mask by peeling one member off at a time and adding one whenever the mask itself sums to zero.

Pythonentry point: min_transfers

def min_transfers(transactions):
    # m = number of members left with a non-zero position, m <= 12.
    # Time O(2^m * m), space O(2^m) for the two subset tables.
    net = {}
    for a, b, amount in transactions:
        net[a] = net.get(a, 0) + amount
        net[b] = net.get(b, 0) - amount
    debts = [v for v in net.values() if v != 0]
    m = len(debts)
    if m == 0:
        return 0
    full = 1 << m
    subset_sum = [0] * full
    for mask in range(1, full):
        low = mask & -mask
        subset_sum[mask] = subset_sum[mask ^ low] + debts[low.bit_length() - 1]
    # groups[mask] = most zero-sum blocks the members in mask can be split into
    groups = [0] * full
    for mask in range(1, full):
        best = 0
        rest = mask
        while rest:
            low = rest & -rest
            if groups[mask ^ low] > best:
                best = groups[mask ^ low]
            rest ^= low
        groups[mask] = best + (1 if subset_sum[mask] == 0 else 0)
    return m - groups[full - 1]

The obvious version

Backtracking over the net positions: take the first member who is not yet at zero and try pushing their whole position onto each member with an opposite sign, recursing on the rest and keeping the cheapest branch.

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_min_transfers(transactions):
    net = {}
    for a, b, amount in transactions:
        net[a] = net.get(a, 0) + amount
        net[b] = net.get(b, 0) - amount
    debts = [v for v in net.values() if v != 0]

    def search(i):
        while i < len(debts) and debts[i] == 0:
            i += 1
        if i == len(debts):
            return 0
        best = float("inf")
        for j in range(i + 1, len(debts)):
            if debts[i] * debts[j] < 0:
                debts[j] += debts[i]
                cost = 1 + search(i + 1)
                debts[j] -= debts[i]
                if cost < best:
                    best = cost
        return best

    return search(0)

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
4 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