Fewest Payments to Settle Up
After a trip, balances[i] says where friend i stands: a positive number is money the others still owe them, a negative number is money they still owe. The balances add up to 0.
One payment moves any amount from one friend to another. Return the fewest payments that bring every balance to 0.
Example 1
balances [10,-4,-6]
returns 2
The two friends who owe money each pay friend 0: two payments.
Example 2
balances [5,-5,3,-3]
returns 2
Friend 1 pays 5 to friend 0 and friend 3 pays 3 to friend 2.
Example 3
balances [4,4,-3,-5]
returns 3
No smaller group cancels out by itself, so the four friends need three payments.
Constraints
1 <= len(balances) <= 10-1000 <= balances[i] <= 1000- the balances add up to 0
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.