Who sends money to whom?
That is the question a shared trip ends on, and pair by pair it gets out of hand. Ana, Bruno, Carla, Dev and Eli spent a week in a rented villa, and the trip app recorded each expense with the people who shared it:
- Ana paid the villa, 800, shared by all five: 160 each.
- Eli paid the car rental, 600, shared by all five: 120 each.
- Bruno paid the groceries, 300, shared by Bruno, Carla and Dev: 100 each.
- Carla paid a boat trip, 180, shared by Ana, Bruno and Carla: 60 each.
- Dev paid a dinner, 240, shared by everyone except Eli: 60 each.
Settled pair by pair, Carla owes Bruno 100 for the groceries and he owes her 60 for the boat, which offsets to 40. Every pair of friends ends up with a debt: ten of them, moving 900. Even Eli, owed more than anyone but Ana, owes Ana 40.
One number per person
Pairs hide the question each friend actually has: across the whole trip, am I up or down? That is the member's net position, what they paid minus their share of everything they took part in.
- Ana paid 800; her share is 160 + 120 + 60 + 60 = 400. Net +400.
- Bruno paid 300; his share is 160 + 120 + 100 + 60 + 60 = 500. Net −200.
- Carla paid 180; her share is also 500. Net −320.
- Dev paid 240; his share is 160 + 120 + 100 + 60 = 440. Net −200.
- Eli paid 600; his share is 160 + 120 = 280. Net +320.
The five numbers sum to zero, and always will: each expense adds its amount to the payer and takes the same amount, in shares, from those who shared it. Any other sum points to an error, such as shares that do not add back to their expense: a cheap check on every recomputation. It cannot catch a whole lost expense, whose credit and shares vanish together.
The goal is now plain: move money from the negatives to the positives until everyone is at zero, whoever paid for what. Replacing the pairwise debts with such a shorter list of transfers is debt simplification, or netting. Each debtor pays exactly what they are down, so the transfers carry 720, against 900 pair by pair. Netting changes who pays whom, never how much anyone is up or down.
Largest debt to largest credit
The usual plan is greedy: match whoever owes the most with whoever is owed the most, move what the smaller of the two needs, and repeat.
- Carla (−320) pays Ana (+400) 320; Ana is still owed 80.
- Bruno (−200) pays Eli (+320) 200; Eli is still owed 120.
- Dev (−200) pays Eli 120; Dev still owes 80.
- Dev pays Ana 80, and both reach zero.
Four transfers instead of ten (taking Dev before Bruno, tied at −200, also gives four), and never more than n − 1. Each transfer moves the smaller of the two amounts, so at least one person reaches zero and drops out. When two people are left, their balances are opposite, since the total is still zero, and one transfer clears both: at most n − 2 transfers, plus one. That is the bound the Expense Splitting brief asks for: at most one transfer fewer than the members.
Three would have done
Look at the positions again. Carla's −320 and Eli's +320 cancel on their own, and Ana's +400 cancels Bruno's and Dev's −200. Two subgroups each sum to zero, and each can settle separately: Carla pays Eli 320, Bruno pays Ana 200, Dev pays Ana 200. Three transfers, and no fewer will do: two transfers touch at most four people, and all five have a balance.
A zero-sum subgroup of k people needs at most k − 1 transfers, by the same argument, so every such subgroup split off saves one. Greedy missed it because its first move, Carla to Ana, cut across both. The true minimum comes from splitting the group into as many zero-sum subgroups as possible, and that search is hard: when anyone may pay anyone, finding the minimum is NP-hard in general, so no known method is fast for every group, and an exact search gets expensive as the group grows. For five friends, trying every split is instant; for a club of 40, it is not something to run on every new coffee, which is why n − 1 is the promise.
The cent nobody can split
Amounts are integers in minor units, cents, never floating point, where 0.1 + 0.2 is not quite 0.3. Integers fix addition, not division: a 100.00 taxi split three ways is 10000 cents, two shares of 3333 and one of 3334. The rule that picks who carries the extra cent must be fixed and written down, for example member-id order; a rule that depends on the order rows come back in moves the cent between people from one recomputation to the next. As long as each expense's shares add up to its amount, the positions still sum to zero.
Netting across currencies needs an exchange rate and a date for it, a choice the arithmetic cannot make, so until a group picks one, net each currency separately.
Store the expenses, derive the plan
None of these numbers is the app's source of truth. It stores records: expenses (who paid, how much, who shared it, how it was split) and payments (who paid whom, how much). Net positions, pairwise balances and the plan are derived from them, either on every read or kept in a cache or a table updated with each record, and can always be rebuilt from them.
Expenses and payments are stored. Net positions and the plan are recomputed from them; the cache can be dropped and rebuilt.
Here is why. The app showed the four-transfer plan, and that evening Carla paid Ana 320; the app stored a payment, which counts like an expense of 320 that Carla paid and Ana alone shared. Next morning Bruno finds the grocery receipt: 360, not 300. He edits the expense, each of the three shares rises from 100 to 120, and the positions become Ana +80, Bruno −160 (he paid 60 more, his share rose 20), Carla −20, Dev −220, Eli +320.
The recomputed plan is Dev pays Eli 220, Bruno pays Eli 100, Bruno pays Ana 60, Carla pays Ana 20. It is not the old plan with new amounts: Dev no longer pays Ana, and Carla, who had settled, owes again. Following the old plan to the end would leave Bruno 40 overpaid and Carla and Dev each owing 20. So a plan is an answer computed from the records as they stood, recomputed whenever one changes; a payment made against an old plan is still a true record, and the next plan accounts for it.
Three neighbouring problems surface here, each with its own article: the payment link the brief asks for, which the provider confirms later, asynchronously (Payments & billing integration); Bruno tapping "Settle up" twice on a slow connection, which must record one payment, not two (Idempotency Key); and Bruno and Dev editing the grocery expense at once, where one edit can silently overwrite the other (Transactions & isolation levels).
Where the plan lives in your design
The Expense Splitting Challenge asks for this app in at most 12 nodes, payment links and notifications included. Its netting line is met by the n − 1 bound; the design decision is where the plan lives. Stored, it needs a rule for what makes it stale; derived from the expense and payment records, it is rebuilt when they change, and the question becomes how soon a cached copy or an open screen catches up. Put Bruno's corrected receipt to your diagram, and see which one you drew and what Carla sees if she opened the plan a minute earlier.