hardBacktrackingIndian domain~40 min
Minimum UPI Transfers to Settle Group Expenses
A group-expense app records who paid whom. To settle up, members send UPI transfers. Given all the IOUs, find the minimum number of transfers needed to bring everyone's net balance to zero.
Problem
Given a list of transactions where transactions[i] = [from, to, amount] means person from paid person to amount rupees, return the minimum number of transfers required to settle all debts so every person's net balance is zero.
Input
A list transactions of [from, to, amount] triples over a small set of people.
Output
An integer: the minimum number of settling transfers.
Constraints
- 1 <= transactions.length <= 8
- 0 <= from, to < 12, from != to
- 1 <= amount <= 100
Examples
Example 1
Input
transactions = [[0,1,10],[2,0,5]]
Output
2
Net balances: person 0 = -5, 1 = +10, 2 = -5; two transfers settle it.
Example 2
Input
transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output
1
Net balances reduce so a single transfer settles everyone.