FunctionRacerProblemsRace

Fewest Payments to Settle Up

HardRecursionPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems