Split the bill. Settle it in as few payments as possible.

The hard part

Three people split €100. Who gets the extra cent — and what is the fewest payments that settles everyone?

1. Money is an integer, and splitting it is not division

Every amount is a whole number of cents. 0.1 + 0.2 !== 0.3 is the famous reason to avoid floats, but the one that bites a splitter is that €33.333… cannot be represented by anything that also adds back up to €100. There is no rounding rule that fixes it — you have to decide who gets the odd cent.

2. Largest remainder, deterministically

Everyone gets the floor of their exact share, then leftover cents go out one at a time, largest fractional part first, ties broken by position. €100 between three → [3334, 3333, 3333]. Deterministic matters: the same expense splits the same way every render, so nobody reloads and finds they owe a different cent than their friend’s screen says.

3. The fewest transfers, and why greedy is not the answer

With n people holding a balance, settling takes n − k transfers, where k is the largest number of groups they can be partitioned into whose balances each sum to zero. Maximising k is subset-sum in a hat — NP-hard. Most implementations stop at greedy (largest debtor pays largest creditor). Usually right. Not always:

Ana −6.00   Ben −6.00   Cal −4.00   Dee +10.00   Eve +6.00

greedy:  4 payments
optimal: 3 payments   (Ana and Eve cancel exactly; greedy never notices)

That case is a test, not a footnote. A bitmask DP over all 2ⁿ subsets finds the true minimum for groups up to 16 — every dinner, house share and holiday — and falls back to greedy above that. The randomised test asserts the plan always settles everyone, never exceeds n − 1 transfers, and is never worse than greedy.

A settlement is not a special case

Paying someone back is the same kind of fact as paying for dinner: balance = paid − share + payments made − payments received. No debt table, no state machine to fall out of sync. Because every term appears once positive and once negative, balances provably sum to zero — and the solver throws if they ever don’t, because that means a bug here.

Running it

It is a server application — Postgres, sessions, and a ledger that has to balance to the cent. This page is a static showcase; the app itself needs somewhere to run. One command does it:

git clone https://github.com/0211IkeVenLouie/evensplit
cd evensplit
docker compose up

That brings up Postgres, runs the migrations and seeds a demo with real data in it, so there is something to look at the moment it boots.

See it for yourself

1. Add an expense split three ways and check the shares add up to the bill exactly.
2. Try entering 12.345. It is rejected, not rounded.
3. Watch the settle-up plan collapse a chain: if Ana owes Ben and Ben owes Cal, Ana pays Cal and Ben never touches the money.

Also in this set