call(back)
Algorithms & Data StructuresmediumSign in to star problems

Settle Debts I

Friends on a trip pay for each other. Payments are recorded as {payer, amount, payees}: the amount is split equally among the payees (the payer may be a payee). Amounts are integer cents; when the split isn't exact, the first amount mod len(payees) payees owe one cent extra.

Implement settle(payments): compute everyone's net balance and return a list of transfers [from, to, amount] that settles all debts. Any valid settlement is accepted, but it must use at most n − 1 transfers for n people with a nonzero balance.

[ {payer: "alice", amount: 4000, payees: ["bob", "jess", "alice", "sam"]},
  {payer: "bob",   amount: 1000, payees: ["alice"]},
  {payer: "sam",   amount: 1000, payees: ["alice"]} ]
=> [["jess", "alice", 1000]]

Hints

Hint 1

Only net balances matter: payer +amount, each payee −share. Anyone at zero drops out of the problem entirely.

Hint 2

Repeatedly match the largest debtor with the largest creditor and transfer min(|debt|, credit) — one side hits zero each round, so at most n − 1 transfers.

Asked at