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.