Minimize Cash Flow among a given set of friends who have borrowed money from each other

Introduction

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.

 

Note: Please try to solve the Minimizing Cash Flow on CodeStudio before stepping into the solution.

Approach 1: Greedy Algorithm

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.

  1. The first step will be to calculate the net amount for every person and store it in an amount array.
    1. Net amount = sum(received money) - sum(sent money).
  2. 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.
  3. Let the minimum of two amounts be 'y'.
  4. If y equals max_credit, delete cred from the list and repeat for the remaining (n-1) people.
  5. If y equals max_debit, delete debt from the group of people and repeat for recursion.
  6. If the amount is 0, then the settlement is done.

Implementation

class Solution
{
//Total no of persons 
static final int n = 3;

//Returns the index of minimum value in arr[]
static int get_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[]
static int get_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
static int min_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].

static void min_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.
static void min_cash(int graph[][])
{
// Create an array amount[],
// initialize all value in it as 0 for storing
//the net amount.
int amount[]=new int[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
public static void main (String[] args)
{
// cash[i][j] means that the amount
//person i has to pay to person j.
int cash[][] = { {020004000},
{003000},
{000},};

// 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

  1. 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.
     
  2. 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.
     
  3. 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.

You can also have a view of the Data Structures and Algorithms guided path to start your preparation from scratch.


Happy Reading!

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think