Minimum cash flow

Easy
0/40
Average time to solve is 10m
profile
Contributed by
20 upvotes
Asked in company
Codenation

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 
0 1000 2000
1000 0 2000
0 1000 0
2 
0 1000
2000 0
Sample Output 1:
3000
1000

Explanation for Sample 1:

The optimal cash flow for the first test case will be-
• Person 1 gives $2000 to person 3.
• Person 2 gives $1000 to person 1.

The optimal cash flow for the second test case will be-
• Person 2 gives $1000 to person 1.
Sample Input 2 :
1
2
0 1000
1000 0
Sample Output 2 :
0
Hint

Try to think about as to how the minimised cash flow system will look like.

Approaches (1)
Greedy 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’.
       
Time Complexity

O(N ^ 2), where ‘N’ denotes the number of friends.

 

The time required to create the array/list ‘BALANCE’ will be O(N ^ 2) as we have to iterate over the whole ‘MONEY' matrix. 

The time required to compute final answer will be O(NlogN) as the maximum size of the multiset can be O(N) and all operation in the multiset takes O(logN) time complexity. 

Thus, the overall time complexity will be O(N ^ 2).

Space Complexity

O(N), where ‘N’ denotes the number of friends.

 

Space required by the array/list ‘BALANCE’ and the multiset will be of O(N) complexity.

Code Solution
(100% EXP penalty)
Minimum cash flow
Full screen
Console