Given n people who owe various amounts of money to each other, simplify the transactions they make between themselves such that there are no more than n transactions and everyone is fairly paid.
Example:
There are four people: sam, jim, bob, sarah
Format is of the form [(from, to, amount)]
Input:
[("sam","jim",200),("sam","bob",110),("jim","bob",50),("jim","sarah",20),("bob","sarah",30),("sarah","sam",120)] This means sam owes jim 200, sam owes bob 110, jim owes bob 50, jim owes sarah 20, bob owes sarah 30, and sarah owes sam 120.
Sample Output:
[("sarah","sam",70),("sam","jim",260),("jim","bob",130)] This means sarah pays sam 70, sam pays jim 260, and jim pays bob 130.
To see why this is correct consider jim. Originally he was going getting 200 and paying 50+20. So overall he was getting 200 - (50 + 20) = 130.
With the simplified transactions he is getting 260 and paying 130. So overall he is getting 260 - 130 = 130.
This same check can be applied to each person to see that this simplification is fair.
Read full article from Simplify Transactions
No comments:
Post a Comment