Last Updated: 10 Dec, 2020

Minimum cash flow

Easy

Asked in company

Solve now

Problem statement

There are ‘N’ friends who have borrowed money from one another. Now, they wanted to settle their debts by giving or taking some money among themselves.

Your task is to design a series of transactions, such that the total cash flow among them is minimized.

For example:

Let there be three friends ‘A’, ‘B’, ‘C’  with debts-

• A has to pay $ 2000 to B.
• A has to pay $ 1000 to C.
• B has to pay $ 3000 to C.
• C has to pay $ 1000 to A.

Then their minimized cash flow system will be-

• A will finally pay $ 2000 to C.
• B will finally pay $ 1000 to C.

Thus, the total cash flow among them will be $ 3000.

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

Then the first line of each test case contains a single integer ‘N’ denoting the number of friends.

The next ‘N’ lines contain ‘N’ space-separated integers where each element money[i][j] denotes the amount of money i-th person has to give to the j-th person.

Output Format :

For each test case, print an integer denoting the minimum cash flow among friends to settle their debt.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 100
1 <= MONEY[i][j] <= 10^5

Time Limit: 1sec

Solve now

Approaches

01 Approach

Let us calculate the net amount for every person by subtracting all the debts(amount to pay) from all credit(amount to be paid to him). We will find the person with the maximum and the minimum net amount. We will greedily do the transaction between them, settle their debts and repeat the same process.

The algorithm will be-

We will construct the array/list ‘BALANCE’, with ‘BALANCE[‘i’]’ storing the net amount for the i-th person.
We will insert all element of ‘BALANCE’ in a multiset ‘TRANSIT’.
While the smallest element of ‘TRANSIT’ is not equal to 0:
- We will take the minimum element ‘MAX_DEBT’ from ‘TRANSIT’.
- We will take the maximum element ‘MIN_DEBT’ from ‘TRANSIT’.
- Increase our final answer by min(absolute(‘MAX_DEBT’), absolute(‘MIN_DEBT’)).
- Remove ‘MAX_DEBT’ and ‘MIN_DEBT’ from ‘TRANSIT’.
- Increase ‘MAX_DEBT’ and decrease ‘MIN_DEBT’ by min(absolute(maxDebt), minDebt).
- Insert ‘MAX_DEBT’ and ‘MIN_DEBT’ back into ‘TRANSIT’.

Solve now