Design Splitwise

Description

Splitwise - tracking who owes whom in a group and settling up - looks like arithmetic and is really about money handling and invariants: amounts that must never lose or invent a cent, a ledger whose balances always sum to zero, split rules that keep growing, and a settle-up that uses few transfers. This skill builds that ledger in integer cents, makes split types pluggable, and settles debts greedily.

Splitwise-style apps look like arithmetic, and the first attempt treats them that way:

Map<String, Double> balance = new HashMap<>();

void addExpense(String payer, double amount, List<String> people) {
    double share = amount / people.size();                  // 10.00 / 3 = 3.3333333333333335
    balance.merge(payer, amount, Double::sum);
    for (String p : people) balance.merge(p, -share, Double::sum);
}

balance: dict[str, float] = {}

def add_expense(payer: str, amount: float, people: list[str]) -> None:
    share = amount / len(people)                      # 10.00 / 3 = 3.3333333333333335
    balance[payer] = balance.get(payer, 0.0) + amount
    for p in people:
        balance[p] = balance.get(p, 0.0) - share

Every line hides a bug that shows up in a test. double can't represent most decimal amounts exactly (0.1 + 0.2 is 0.30000000000000004), so balances end up as -0.0000000001 and "is everyone even?" is never quite true. Three people splitting 10.00 each owe a third of a cent more than can be paid, and someone has to absorb that cent. An unknown participant throws halfway through the loop, after the payer was already credited. And "settle up" usually means one payment per debt, when most of them could cancel out.

We'll go from simple to more technical:

1. The model: expenses, splits and a pairwise ledger in cents.
2. Splitting exactly, including the leftover cent.
3. Settling up with at most n - 1 transfers.
4. The bugs that lose or invent money, and the tradeoffs in what to store.

The approach

1. Clarify. Which split types - equally, exact amounts, percentages, shares? What currency and precision; who gets the leftover cent? Can the payer be left out of the split? Should settling up minimize transfers? Can expenses be edited? (Multiple currencies and groups are common follow-ups; agree they're out of scope first.)
2. Model. Money as a long count of cents (an int in Python, which never overflows). A SplitStrategy interface with one class per split type. A Transfer record for settle-up plans. An ExpenseManager that owns the users and the ledger.
3. API. addUser(id), addExpense(paidBy, amountCents, split), recordPayment(from, to, amountCents), balanceOf(id), owes(from, to), settleUp().
4. Core. A ledger of pairwise net debts, updated on both sides together, and a greedy settle-up over the net balances.

The pieces in code

Each split type answers one question - who owes how much of this amount? - so it's a strategy:

public interface SplitStrategy {
    Map<String, Long> shares(long amountCents);   // always adds up to amountCents
}

public class EqualSplit implements SplitStrategy {
    private final List<String> participants;
    // constructor rejects an empty list or a duplicate

    public Map<String, Long> shares(long amountCents) {
        int n = participants.size();
        long each = amountCents / n, leftover = amountCents % n;
        Map<String, Long> shares = new LinkedHashMap<>();
        for (int i = 0; i < n; i++) shares.put(participants.get(i), each + (i < leftover ? 1 : 0));
        return shares;
    }
}

from abc import ABC, abstractmethod


class SplitStrategy(ABC):
    @abstractmethod
    def shares(self, amount_cents: int) -> dict[str, int]: ...    # always adds up to amount_cents


class EqualSplit(SplitStrategy):
    def __init__(self, participants: list[str]):
        # rejects an empty list or a duplicate
        self._participants = participants

    def shares(self, amount_cents: int) -> dict[str, int]:
        each, leftover = divmod(amount_cents, len(self._participants))
        return {p: each + (1 if i < leftover else 0) for i, p in enumerate(self._participants)}

1000 cents among three is 334, 333 and 333: rounded down, and the leftover cent handed to the first participant by a rule that's written down and deterministic. PercentSplit does the same with a percentage per person (round down, hand out the leftover in a fixed order), and ExactSplit simply checks that the given shares add up.

The ledger keeps one number per pair, stored on both sides:

/** net.get(a).get(b) > 0 means a owes b that much; always net[a][b] == -net[b][a]. */
private final Map<String, Map<String, Long>> net = new HashMap<>();

public void addExpense(String paidBy, long amountCents, SplitStrategy split) {
    if (amountCents <= 0) throw new IllegalArgumentException("The amount must be positive");
    requireUser(paidBy);
    Map<String, Long> shares = split.shares(amountCents);       // may throw: nothing has changed yet
    for (String p : shares.keySet()) requireUser(p);           // validate everything first...
    for (var e : shares.entrySet())                            // ...then apply everything
        if (!e.getKey().equals(paidBy)) move(e.getKey(), paidBy, e.getValue());
}

private void move(String a, String b, long amount) {          // a owes b `amount` more
    net.get(a).merge(b, amount, Long::sum);
    net.get(b).merge(a, -amount, Long::sum);
}

def __init__(self):
    # net[a][b] > 0 means a owes b that much; always net[a][b] == -net[b][a]
    self._net: dict[str, dict[str, int]] = {}

def add_expense(self, paid_by: str, amount_cents: int, split: SplitStrategy) -> None:
    if amount_cents <= 0:
        raise ValueError("The amount must be positive")
    self._require_user(paid_by)
    shares = split.shares(amount_cents)           # may raise: nothing has changed yet
    for p in shares:
        self._require_user(p)                     # validate everything first...
    for p, share in shares.items():               # ...then apply everything
        if p != paid_by:
            self._move(p, paid_by, share)

def _move(self, a: str, b: str, amount: int) -> None:    # a owes b `amount` more
    self._net[a][b] = self._net[a].get(b, 0) + amount
    self._net[b][a] = self._net[b].get(a, 0) - amount

• Both sides in one place. move is the only code that touches the ledger, so "what A owes B" and "what B owes A" can't disagree. If A owes B 500 and later B owes A 200, the pair simply nets to 300.
• Derived numbers are derived. owes(a, b) is max(0, net[a][b]); balanceOf(a) is minus the sum of a's row. A payment is just a move in the other direction, and overpaying flips the debt.
• All or nothing. Every check runs before the first move, so a rejected expense changes nothing.

Settling up

Only net balances matter for settling: if A owes B and B owes C the same amount, A can pay C and B does nothing. The greedy plan:

while someone's balance is negative:
    debtor   = the most negative balance   (ties: alphabetically first)
    creditor = the most positive balance   (ties: alphabetically first)
    amount   = min(-balance[debtor], balance[creditor])
    record a transfer (debtor, creditor, amount) and update both balances

Every transfer brings at least one of the two to exactly zero, and the last one brings both, so n people with non-zero balances need at most n - 1 transfers. The plan is computed on a copy - settleUp proposes payments; recordPayment is what changes the ledger when money actually moves.

Where you'll see it

Real expense apps are ledgers. Expenses and payments are immutable entries; editing an expense writes a reversing entry plus a new one, so every balance can be explained from history and audited. Payment requests carry an idempotency key, so a mobile client that retries after a timeout doesn't record the same payment twice. Multi-currency groups store each entry in its own currency and convert at a recorded rate when settling. And the rounding rule is part of the product spec, because users will ask where the extra cent went.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Three friends split a 10.00 dinner equally. What does each owe, and what property must the shares always have?

2. A owes B 500 from one dinner; later B owes A 200 from a taxi. What do owes(A, B), owes(B, A) and A's balance return?

3. Why can greedy settle-up never need more than n - 1 transfers for n people with non-zero balances?

Key takeaways

• Money is a long count of cents (or BigDecimal), never double; shares round down and the leftover cents follow a fixed, documented rule.
• Each split type is a SplitStrategy returning shares that add up to the amount - a new split type is a new class.
• Keep a pairwise net ledger updated on both sides by one method; balances and "who owes whom" are derived from it.
• Validate the whole entry before applying any of it, so a rejected expense changes nothing.
• Greedy settle-up (largest debtor pays largest creditor) needs at most n - 1 transfers; the true minimum is NP-hard, so greedy is what ships.