Four friends, six debts, settled in three payments

transcript

Four friends. One Goa trip. Five expenses. Everyone owes someone. Six debts. Settled in three payments.

Forget who owes whom. Give each person one number: their net balance. Aarav is owed the most. Kabir is owed 1,600. Diya and Meera owe. And all four sum to exactly zero.

Now be greedy. Take the biggest debtor. And the biggest creditor. One pays the other the smaller of the two amounts. At least one of them hits zero and leaves. Repeat.

Meera owes the most. She pays Aarav everything she owes. She's done. Diya pays Kabir 1,600. Kabir's done. Diya pays Aarav the rest. Everyone's at zero. Three payments.

Each round removes a person. So at most n minus 1 payments. Usually optimal, or close. But not always the minimum. The true minimum is NP-hard in general. Say that out loud. And Diya owed Kabir 950. The plan has her pay him 1,600.

That's why most apps make simplifying a group setting. Settle the net balances. Not every debt.

Full breakdown in the lecture.