This problem is asked in one of the top companies like Amazon. If you are aiming for such companies, then this problem is a must.
What do you mean by minimizing cash flow?
Let's understand this with the help of the problem statement.
Problem Statement
Suppose you are given that there are few friends. They have borrowed money from each other due to which there will be some cash flow on the network. Our main aim is to design an algorithm by which the total cash flow among all the friends is minimized.
For example:
There are three friends A1, A2, A3; you have to show the settlement of input debts between them.
The approach we will be using for minimizing cash flow is the Greedy Algorithm. The greedy approach is used to build the solution in pieces, and this is what we want to minimize the cash flow. At every step, we will settle all the amounts of one person and recur for the remaining n-1 persons.
Calculate the net amount for every person, which can be calculated by subtracting all the debts, i.e., the amount to be paid from all credit, i.e., the amount to be paid to him. After this, we will find two persons with the maximum and the minimum net amounts. The person with a minimum of two is our first person to be settled and removed from the list.
Following algorithm will be done for every person varying 'i' from 0 to n-1.
The first step will be to calculate the net amount for every person and store it in an amount array.
Net amount = sum(received money) - sum(sent money).
Find the two people that have the most credit and the most debt. Let the maximum amount to be credited from maximum creditor be max_credit and the maximum amount to be debited from maximum debtor be max_debit. Let the maximum debtor be debt and maximum creditor be cred.
Let the minimum of two amounts be 'y'.
If y equals max_credit, delete cred from the list and repeat for the remaining (n-1) people.
If y equals max_debit, delete debt from the group of people and repeat for recursion.
classSolution { //Total no of persons staticfinalint n = 3;
//Returns the index of minimum value in arr[] staticintget_min(int arr[]) { int in = 0; for (int i = 1; i < n; i++) if (arr[i] < arr[in]) in = i; return in; }
//Returns the maximum index in arr[] staticintget_max(int arr[]) { int in = 0; for (int i = 1; i < n; i++) if (arr[i] > arr[in]) in = i; return in; }
//Function which return the minimum of 2 values staticintmin_two(int x, int y) { return (x < y) ? x: y; }
//Here amount array is storing the net amount to be settled //to/from person p(i), now if amount[p] is +ve then ith person //give amount[i] otherwise amount[p] will give -amount[i].
staticvoidmin_cashRec(int amount[]) { // Find the indexes of minimum and // maximum values in amount[] // amount[max_credit] indicates the maximum amount // that to be given to the person. // And amount[max_debit] indicates the maximum amount // to be taken from a person. //Along with the positive value there will also be negative value int max_credit = get_max(amount), max_debit = get_min(amount);
//amounts to be 0 for the settlement if (amount[max_credit] == 0 && amount[max_debit] == 0) return;
// Find the minimum of two amounts int min = min_two(-amount[max_debit], amount[max_credit]); amount[max_credit] -= min; amount[max_debit] += min;
// If the minimum is the maximum amount to be System.out.println("Person " + max_debit + " pays " + min + " to " + "Person " + max_credit);
//recur for remaining persons min_cashRec(amount); }
// Given a set of persons as graph[] // where graph[i][j] indicates // the amount that person i needs to // pay person j, this function //finds and settles the debts. staticvoidmin_cash(int graph[][]) { // Create an array amount[], // initialize all value in it as 0 for storing //the net amount. int amount[]=newint[n];
// Calculate the net amount to // be paid to person 's', and // stores it in amount[s]. The // value of amount[s] an be //calculated by subtracting //sum of all received money - sum of all sent money.
for (int s = 0; s < n; s++) for (int i = 0; i < n; i++) amount[s] += (graph[i][s] - graph[s][i]);
min_cashRec(amount); }
// Main function publicstaticvoidmain (String[] args) { // cash[i][j] means that the amount //person i has to pay to person j. int cash[][] = { {0, 2000, 4000}, {0, 0, 3000}, {0, 0, 0},};
// Print the solution min_cash(cash); } }
Output
Person 0 pays 6000 to Person 2 Person 1 pays 1000 to Person 2
Complexity Analysis
Time Complexity: The time complexity of minimizing the cash flow is O(n^2). Where n = number of persons.
Space Complexity:
Frequently asked questions
What do you mean by minimizing cash flow? Here minimizing cash flow means how efficiently or conveniently you can make a flow of cash transfer among your friends.
What do you mean by Greedy Algorithm? Greedy is an algorithmic approach that assembles a solution piece by piece, constantly opting for the next piece that provides the most evident and immediate benefit. Greedy is best suited to problems when picking locally optimal leads to a global solution.
What is the time complexity of this approach? The time complexity of this approach efficiently is O(n^2), where n is equal to the number of persons.
Key Takeaways
In this blog, we discuss the problem's solution, where we have to minimize the cash flow among the friends.
We see the implementation of minimizing cash flow problems in the Java language. Apart from this, you can practice more questions similar to this problem or on a Greedy algorithm like Find minimum time to finish all jobs with given constraints, Find maximum sum possible equal to the sum of three stacks, and many more.
38+ registered 