Fewest transfers was correct. It also told a stranger to pay my friend.

The plan said Coco pays Mia $75.20.

The arithmetic was right. Coco and Mia have never met. Coco wasn't even on the trip.

This is about the settle-up screen in the expense splitting I built for my travel app (BeforeGo, iOS). The problem got caught in a worked example before it shipped, and the fix is small. I still think it's worth writing up, because the textbook algorithm does exactly what it promises, and that turned out to be the problem.

Two kinds of people on a trip's bills

Most splitting apps assume everyone on a bill is in the group. On a real trip, that's not quite true:

• Buddies: the people on the trip. They pay for things and split things with each other.
• Others: friends back home you bought things for. If you've been to a Japanese drugstore with a shopping list from three friends, you know.

Others show up on exactly one kind of bill: one you paid on their behalf. They don't owe the group anything. They owe you.

The textbook settle-up

The usual way to settle a group's debts:

1. Work out each person's net: what they paid minus what they owe. Positive means they're owed money.
2. Pair the largest creditor with the largest debtor, transfer as much as possible, and repeat until everyone's at zero.

Each step zeroes at least one person, so with n people you never need more than n − 1 transfers. It isn't guaranteed to find the true minimum (that problem is NP-hard: it comes down to finding as many separate zero-sum groups as possible), but it's simple, it's predictable, and on a trip-sized group it's hard to beat.

Here's the version in the app, trimmed:

/// Greedy: the largest creditor takes from the largest debtor until one of them is square. /// Scanning in roster order and replacing only on a strictly larger amount makes ties go to /// whoever comes first on the roster. private static func fewestTransfers(_ net: [UUID: Decimal], roster: [UUID]) -> [SettlementTransfer] { var credits: [(id: UUID, amount: Decimal)] = roster.compactMap { id in guard let value = net[id], value > 0 else { return nil } return (id, value) } var debts: [(id: UUID, amount: Decimal)] = roster.compactMap { id in guard let value = net[id], value < 0 else { return nil } return (id, -value) } // largest(_:) returns the index of the biggest amount; the first one wins a tie. var transfers: [SettlementTransfer] = [] while !credits.isEmpty, !debts.isEmpty { let c = largest(credits) let d = largest(debts) let amount = min(credits[c].amount, debts[d].amount) transfers.append(SettlementTransfer(fromId: debts[d].id, toId: credits[c].id, amount: amount)) credits[c].amount -= amount debts[d].amount -= amount if credits[c].amount == 0 { credits.remove(at: c) } if debts[d].amount == 0 { debts.remove(at: d) } } return transfers } 

The worked example

Before writing any of the money code, the design doc had one sample trip worked out with exact fractions: five bills in Tokyo, three buddies (Me, Mia, Leo) and two friends back home (Coco, Ray). Rate: 1 JPY = 0.0067 USD.

Put everyone in one pool and the nets are:

They add up to zero, as they should. Run the greedy on that pool and you get:

• Leo → Mia $250.31
• Me → Mia $80.00
• Coco → Mia $75.20
• Ray → Mia $37.63

Four transfers, the minimum for this set (there's only one creditor, so each of the four debtors has to pay someone). Every number checks out.

And it's absurd. Coco would be sending money to someone she's never met, for sunscreen I bought her, including my 10% shopping fee. Meanwhile I'd pay Mia $80 instead of the $192.83 I actually owe her, because my friends back home would be covering the rest of what I owe her.

The algorithm minimised the number of transfers. Nobody had told it that money only moves between people who know each other.

The fix: two ledgers, not one

Buddies net against each other and get the fewest-transfers plan. Anyone else settles one-to-one with whoever paid their bills, and never joins the buddies' pool.

In code, it's one branch where each debt gets recorded:

func owe(_ debtor: UUID, _ creditor: UUID, _ amount: Decimal) { guard debtor != creditor, amount != 0 else { return } if buddies.contains(debtor), buddies.contains(creditor) { buddyNet[debtor, default: 0] -= amount buddyNet[creditor, default: 0] += amount } else if debtor.uuidString < creditor.uuidString { // Unordered pair → balance; positive means `low` owes `high`. pairs[PairKey(low: debtor, high: creditor), default: 0] += amount } else { pairs[PairKey(low: creditor, high: debtor), default: 0] -= amount } } 

buddyNet goes through fewestTransfers. pairs turns straight into one transfer per pair. A recorded payment ("Mark paid") goes through the same owe in the opposite direction, so it nets exactly like a bill.

Same sample, new plan:

• Leo → Mia $250.31
• Me → Mia $192.83
• Coco → Me $75.20
• Ray → Me $37.63

Still four transfers. In this example the sensible plan costs nothing extra. In general it can cost a few: if Coco owes me and I owe Mia, the pooled version can route Coco straight to Mia and save a transfer. That's a transfer worth paying for.

Pinning it down with invariants

The sample is pinned in the tests twice, settled in USD and in CNY, because every number on every mock-up came from it. On top of that, a handful of properties have to hold for any input:

private func assertInvariants(_ bills: [ExpenseSnapshot], _ settlements: [SettlementSnapshot] = [], ledger: TripLedger) { for bill in bills { let breakdown = ExpenseMath.breakdown(of: bill, ledger: ledger) XCTAssertEqual(breakdown.shares.values.reduce(0, +), breakdown.convertedTotal, "shares must add up to the bill") } let plan = ExpenseMath.settle(bills, settlements: settlements, ledger: ledger) XCTAssertEqual(plan.buddyNet.values.reduce(0, +), 0, "buddy nets must add up to 0") XCTAssertEqual(plan.net.values.reduce(0, +), 0, "everyone's nets must add up to 0") let outsiders = Set(plan.net.keys).subtracting(ledger.buddyIds) for transfer in plan.transfers { XCTAssertFalse(outsiders.contains(transfer.fromId) || outsiders.contains(transfer.toId), "an outsider in the buddies' plan") } } 

The first one is the one rounding tries hardest to break. Each share is converted and rounded half-up to the settlement currency's smallest unit, and whatever the rounded shares miss of the rounded total goes to the payer. That's why the dinner splits as $27.88 for me and $27.87 each for Mia and Leo: I paid, so I carry the extra cent.

The same invariants run against the sample at rates from 0.0068 up to 149.37, and in KRW, a currency with no minor unit. The last check in that function is the Coco-and-Mia rule, written so it can't come back.

Two smaller rules came out of the same sample:

• Ties go to roster order. Two people owed the same amount always come out in the same order, and shuffling the bills gives the same plan. The plan is shown on screen, exported as an image and recomputed whenever a bill changes, so it shouldn't reshuffle when nothing has changed.
• No rate, no conversion. A bill in a currency with no exchange rate yet is left out of the totals and flagged. It doesn't get treated as 1:1.

What I took from it

The greedy didn't have a bug. It answered the question I asked: how do these balances clear in as few payments as possible? The question I should have asked was: who would actually send money to whom? Who knows whom is part of the input, and no amount of testing the algorithm would have shown me that.

What caught it was a worked example with real-looking names, done before the code existed. "Coco pays Mia" looks fine in a unit test full of UUIDs. Next to the sentence "Coco wasn't on the trip," it's obviously wrong.

If you've built splitting logic: how do you handle people who aren't part of the group? I'd like to know whether anyone has found a cleaner model than two ledgers.

This post was written by an AI agent (Claude) working from BeforeGo's code, design notes and tests, at my request. Every number and code excerpt in it was checked against them before publishing.