Split group expenses equally and see who pays whom. Find the fewest payments for up to 16 non-zero balances, with an approximate plan for larger groups.
By AdminDrafted with AI writing toolsUpdated Checked examples: 4
Total spent: $195.50; each person's share: $48.88. 3 payments settle everything: Jo pays Alex $48.88; Priya pays Alex $18.88; Sam pays Alex $3.38.
| From | To | Amount |
|---|---|---|
| Jo | Alex | $48.88 |
| Priya | Alex | $18.88 |
| Sam | Alex | $3.38 |
In the formula, P_i is what each person paid, n the group size, q the equal share, b_i each balance, k the number of non-zero balances and G_max the largest number of zero-sum groups. N_min is the minimum payment count, found by exact search only up to 16 non-zero balances.
Alex 120 − 48.875 = 71.125; Sam 45.5 − 48.875 = −3.375; Priya 30 − 48.875 = −18.875; Jo 0 − 48.875 = −48.875
There are 4 non-zero balances. Each zero-sum group of g people settles in g − 1 payments: 3 in total.
Amounts are rounded to the cent for display, so a payment can differ from the exact balance by less than a cent.
Each person's share is the total spent divided by the number of people. A balance is what someone paid minus that share: a positive balance is owed money and a negative one owes it. The calculator then splits the balances into as many groups as possible whose balances cancel out exactly, because a group of g people can always settle in g − 1 payments.
With the defaults, Alex, Sam and Priya paid 195.50 between them and Jo paid nothing, so each share is 48.875. Three payments settle everything: Jo pays Alex 48.88, Priya pays Alex 18.88 and Sam pays Alex 3.38.
Finding the fewest payments is NP-hard in general (Verhoeff, 2004), so the exact search runs when up to 16 people have a non-zero balance; larger groups fall back to paying the largest creditor from the largest debtor. Payments are shown to the cent, so each can differ from the exact balance by less than a cent.
When a group shares all costs equally, add up everything spent and divide by the number of people to get each share. A person's balance is what they paid minus that share: positive means they get money back, negative means they owe. If four people spent 195.50, each share is 48.875.
Alex paid 120, Sam 45.50 and Priya 30. Jo paid nothing but shares the costs.
The three debts add up to 71.125, exactly Alex's credit. Credits and debts always cancel, so if yours do not, an amount was copied wrong.
If k people have a nonzero balance, k − 1 payments always suffice, since each payment can clear at least one person. Fewer are possible when the balances split into groups that cancel out: a group of g people settles in g − 1 payments.
Five people paid 14, 13, 12, 5 and 6. The share is 10, so the balances are +4, +3, +2, −5 and −4. E pays A 4, which closes one group; D pays B 3 and C 2, which closes the other. That is 3 payments.
Paying the largest creditor from the largest debtor first takes 4 payments for the same group. Finding the best grouping is NP-hard in general (Verhoeff, 2004), so it takes a search.
The search is exact when up to 16 people owe or are owed; people who are already even do not count. Larger groups are matched largest-first, which still settles every balance exactly but may use a few extra payments.
A share of 48.875 is not a whole number of cents, so no settlement in cents can be exact. Rounded, the three payments are 48.88, 18.88 and 3.38. They total 71.14, so Alex receives 1.5 cents more than the exact 71.125.
Round only the final payments. Rounding the share to 48.88 first makes the four shares total 195.52, and the books stop balancing: Alex's credit drops to 71.12 while the debts still add up to 71.14.
Any total that does not divide evenly behaves this way. When one person pays 10 for three people, each share is 3.333…, and after two payments of 3.33 the payer's own cost is 3.34.
Split each cost among the people who actually shared it, then add each person's balances across the splits. Say Alex paid 400 for a hotel shared by all four, and Sam paid 60 for train tickets for Sam and Priya only.
Three payments settle the net balances: Sam pays Alex 70, Priya pays Alex 130 and Jo pays Alex 100. Settling the two splits separately takes four, because Priya would also pay Sam 30.
| Scenario | Total spent | Equal share | Payments |
|---|---|---|---|
| Default | 195.500000 | 48.875000 | 3.000000 |
| Minimum beats greedy | 50.000000 | 10.000000 | 3.000000 |
| Everyone even | 30.000000 | 10.000000 | 0.000000 |
| Added payer | 120.000000 | 40.000000 | 1.000000 |
| Repeating share | 10.000000 | 3.333333 | 2.000000 |
Alex paid 120 for food or Alex, 120, food. The description is optional, and several lines for one person add up.ALEX LEE and Alex Lee are one person, even with a double space between the names.To estimate costs before anyone pays, use the travel budget calculator. For a single restaurant bill with a tip, the tip calculator splits the total and the gratuity.
Checked against: 195.50/4 = 48.875; balances −48.875, −18.875, −3.375 rounded half-even to cents; 3 payments by brute-force subset search
Checked against: Brute-force partition into zero-sum groups {A, E}, {B, C, D}: 5 − 2 = 3; largest-first greedy gives 4
Checked against: Definition: every balance is 0
Checked against: Hand calculation: 120/3 = 40; Alex +20, Sam −20, Kim 0
Add up everything spent, divide by the number of people to get the equal share, then subtract that share from what each person paid. For 195.50 spent across four people the share is 48.875: Alex, who paid 120, is owed 71.125, and Jo, who paid nothing, owes 48.875. Everyone with a negative balance pays someone with a positive one.
At most one fewer than the number of people with a non-zero balance, and fewer when the balances split into groups that cancel out, since each group of g people needs g − 1 payments. Tom Verhoeff's 2004 paper shows that finding the minimum is at least as hard as the subset-sum problem, so an exact answer needs a search.
It can miss groups that cancel out. With balances of +4, +3, +2, −5 and −4 (people A to E in the worked example), matching the largest amounts first takes 4 payments. Splitting them into {+4, −4} and {+3, +2, −5} settles the first pair in 1 payment and the trio in 2, so 3 in total.
This splitter shares every cost equally among everyone listed. For a cost that only some people share, such as two people's train tickets, run it separately with just those people, then add the payments from both runs. The combined list settles every debt, though it may use one or two more payments than a single optimised plan.
This calculator includes 4 worked examples with independently sourced answers. They run in the test suite, and you can run them here too.