splitHow settle up works
After a trip or a month in a shared house, everyone has paid for different things. Settling up means working out a list of payments that leaves everyone even. You could have everyone pay back every single expense, but that’s a lot of transfers. split finds the shortest list it can.
Step 1: balances
For each person, split adds up what they paid and subtracts their share of everything. A positive balance means the group owes them money; a negative one means they owe the group. All the balances always add up to exactly zero.
Step 2: the fewest payments
Say the balances are: Ana +£60, Ben +£20, Cy −£50, Dee −£30. A straightforward plan pays off the biggest debt to the biggest creditor first:
- Cy pays Ana £50
- Dee pays Ana £10
- Dee pays Ben £20
Three payments for four people. With n people who aren’t already even, you never need more than n − 1 payments, and this method always stays within that.
When you can do better
Sometimes a group splits into smaller groups that already cancel out. Take Ana +£40, Ben +£25, Cy −£25, Dee −£40. The obvious pairing works: Dee pays Ana £40 and Cy pays Ben £25. That’s two payments, not three, because {Ana, Dee} and {Ben, Cy} each add up to zero on their own.
The rule is: fewest payments = people with a balance − the most separate groups that each add up to zero. Each such group needs one fewer payment than it has people.
Finding those groups is a hard search problem in general, because the number of ways to split people into groups grows very fast. For groups of up to 16 people with open balances, split checks every combination, so the plan you see uses the fewest possible payments. Bigger groups use the step-by-step method above, which is still at most n − 1 payments.
Pennies and currencies
- All amounts are stored as whole cents (or pennies, or yen), so nothing gets lost to rounding.
- When an expense doesn’t divide evenly, the odd cents go to different people on different expenses rather than always the same person.
- Expenses in other currencies are converted with the rate saved on that expense, so the plan doesn’t change when exchange rates move.
split does arithmetic, not financial advice. Check amounts before you send money.