Design a Program to Record Transaction Graphicly

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

Given a number of friends who have to give or take some amount of money from one another. Design an algorithm by which the total cash flow among all the friends is minimized.

Example:

Try Amazon Test Series that Includes topic-wise practice questions on all important DSA topics along with 10 practice contests of 2 hours each. Designed with years of experience.

Following diagram shows input debts to be settled.

Above debts can be settled in following optimized way

The idea is to use Greedy algorithm where at every step, settle all amounts of one person and recur for remaining n-1 persons.
How to pick the first person? To pick the first person, calculate the net amount for every person where net amount is obtained by subtracting all debts (amounts to pay) from all credits (amounts to be paid). Once net amount for every person is evaluated, find two persons with maximum and minimum net amounts. These two persons are the most creditors and debtors. The person with minimum of two is our first person to be settled and removed from list. Let the minimum of two amounts be x. We pay 'x' amount from the maximum debtor to maximum creditor and settle one person. If x is equal to the maximum debit, then maximum debtor is settled, else maximum creditor is settled.
The following is detailed algorithm.

Do following for every person Pi where i is from 0 to n-1.

1. Compute the net amount for every person. The net amount for person 'i' can be computed by subtracting sum of all debts from sum of all credits.
2. Find the two persons that are maximum creditor and maximum debtor. Let the maximum amount to be credited maximum creditor be maxCredit and maximum amount to be debited from maximum debtor be maxDebit. Let the maximum debtor be Pd and maximum creditor be Pc.
3. Find the minimum of maxDebit and maxCredit. Let minimum of two be x. Debit 'x' from Pd and credit this amount to Pc
4. If x is equal to maxCredit, then remove Pc from set of persons and recur for remaining (n-1) persons.
5. If x is equal to maxDebit, then remove Pd from set of persons and recur for remaining (n-1) persons.

Thanks to Balaji S for suggesting this method in a comment here.

The following is the implementation of the above algorithm.

C++

#include<iostream>

using namespace std;

#define N 3

int getMin( int arr[])

{

int minInd = 0;

for ( int i=1; i<N; i++)

if (arr[i] < arr[minInd])

minInd = i;

return minInd;

}

int getMax( int arr[])

{

int maxInd = 0;

for ( int i=1; i<N; i++)

if (arr[i] > arr[maxInd])

maxInd = i;

return maxInd;

}

int minOf2( int x, int y)

{

return (x<y)? x: y;

}

void minCashFlowRec( int amount[])

{

int mxCredit = getMax(amount), mxDebit = getMin(amount);

if (amount[mxCredit] == 0 && amount[mxDebit] == 0)

return ;

int min = minOf2(-amount[mxDebit], amount[mxCredit]);

amount[mxCredit] -= min;

amount[mxDebit] += min;

cout << "Person " << mxDebit << " pays " << min

<< " to " << "Person " << mxCredit << endl;

minCashFlowRec(amount);

}

void minCashFlow( int graph[][N])

{

int amount[N] = {0};

for ( int p=0; p<N; p++)

for ( int i=0; i<N; i++)

amount[p] += (graph[i][p] -  graph[p][i]);

minCashFlowRec(amount);

}

int main()

{

int graph[N][N] = { {0, 1000, 2000},

{0, 0, 5000},

{0, 0, 0},};

minCashFlow(graph);

return 0;

}

Java

class GFG

{

static final int N = 3 ;

static int getMin( int arr[])

{

int minInd = 0 ;

for ( int i = 1 ; i < N; i++)

if (arr[i] < arr[minInd])

minInd = i;

return minInd;

}

static int getMax( int arr[])

{

int maxInd = 0 ;

for ( int i = 1 ; i < N; i++)

if (arr[i] > arr[maxInd])

maxInd = i;

return maxInd;

}

static int minOf2( int x, int y)

{

return (x < y) ? x: y;

}

static void minCashFlowRec( int amount[])

{

int mxCredit = getMax(amount), mxDebit = getMin(amount);

if (amount[mxCredit] == 0 && amount[mxDebit] == 0 )

return ;

int min = minOf2(-amount[mxDebit], amount[mxCredit]);

amount[mxCredit] -= min;

amount[mxDebit] += min;

System.out.println( "Person " + mxDebit + " pays " + min

+ " to " + "Person " + mxCredit);

minCashFlowRec(amount);

}

static void minCashFlow( int graph[][])

{

int amount[]= new int [N];

for ( int p = 0 ; p < N; p++)

for ( int i = 0 ; i < N; i++)

amount[p] += (graph[i][p] - graph[p][i]);

minCashFlowRec(amount);

}

public static void main (String[] args)

{

int graph[][] = { { 0 , 1000 , 2000 },

{ 0 , 0 , 5000 },

{ 0 , 0 , 0 },};

minCashFlow(graph);

}

}

Python3

N = 3

def getMin(arr):

minInd = 0

for i in range ( 1 , N):

if (arr[i] < arr[minInd]):

minInd = i

return minInd

def getMax(arr):

maxInd = 0

for i in range ( 1 , N):

if (arr[i] > arr[maxInd]):

maxInd = i

return maxInd

def minOf2(x, y):

return x if x < y else y

def minCashFlowRec(amount):

mxCredit = getMax(amount)

mxDebit = getMin(amount)

if (amount[mxCredit] = = 0 and amount[mxDebit] = = 0 ):

return 0

min = minOf2( - amount[mxDebit], amount[mxCredit])

amount[mxCredit] - = min

amount[mxDebit] + = min

print ( "Person " , mxDebit , " pays " , min

, " to " , "Person " , mxCredit)

minCashFlowRec(amount)

def minCashFlow(graph):

amount = [ 0 for i in range (N)]

for p in range (N):

for i in range (N):

amount[p] + = (graph[i][p] - graph[p][i])

minCashFlowRec(amount)

graph = [ [ 0 , 1000 , 2000 ],

[ 0 , 0 , 5000 ],

[ 0 , 0 , 0 ] ]

minCashFlow(graph)

C#

using System;

class GFG

{

static int N = 3;

static int getMin( int []arr)

{

int minInd = 0;

for ( int i = 1; i < N; i++)

if (arr[i] < arr[minInd])

minInd = i;

return minInd;

}

static int getMax( int []arr)

{

int maxInd = 0;

for ( int i = 1; i < N; i++)

if (arr[i] > arr[maxInd])

maxInd = i;

return maxInd;

}

static int minOf2( int x, int y)

{

return (x < y) ? x: y;

}

static void minCashFlowRec( int []amount)

{

int mxCredit = getMax(amount), mxDebit = getMin(amount);

if (amount[mxCredit] == 0 &&

amount[mxDebit] == 0)

return ;

int min = minOf2(-amount[mxDebit], amount[mxCredit]);

amount[mxCredit] -= min;

amount[mxDebit] += min;

Console.WriteLine( "Person " + mxDebit +

" pays " + min + " to " +

"Person " + mxCredit);

minCashFlowRec(amount);

}

static void minCashFlow( int [,]graph)

{

int []amount= new int [N];

for ( int p = 0; p < N; p++)

for ( int i = 0; i < N; i++)

amount[p] += (graph[i,p] - graph[p,i]);

minCashFlowRec(amount);

}

public static void Main ()

{

int [,]graph = { {0, 1000, 2000},

{0, 0, 5000},

{0, 0, 0},};

minCashFlow(graph);

}

}

PHP

<?php

$N = 3;

function getMin( $arr )

{

global $N ;

$minInd = 0;

for ( $i = 1; $i < $N ; $i ++)

if ( $arr [ $i ] < $arr [ $minInd ])

$minInd = $i ;

return $minInd ;

}

function getMax( $arr )

{

global $N ;

$maxInd = 0;

for ( $i = 1; $i < $N ; $i ++)

if ( $arr [ $i ] > $arr [ $maxInd ])

$maxInd = $i ;

return $maxInd ;

}

function minOf2( $x , $y )

{

return ( $x < $y )? $x : $y ;

}

function minCashFlowRec( $amount )

{

$mxCredit = getMax( $amount );

$mxDebit = getMin( $amount );

if ( $amount [ $mxCredit ] == 0 &&

$amount [ $mxDebit ] == 0)

return ;

$min = minOf2(- $amount [ $mxDebit ], $amount [ $mxCredit ]);

$amount [ $mxCredit ] -= $min ;

$amount [ $mxDebit ] += $min ;

echo "Person " . $mxDebit . " pays " . $min . " to Person " . $mxCredit . "\n" ;

minCashFlowRec( $amount );

}

function minCashFlow( $graph )

{

global $N ;

$amount = array_fill (0, $N , 0);

for ( $p = 0; $p < $N ; $p ++)

for ( $i = 0; $i < $N ; $i ++)

$amount [ $p ] += ( $graph [ $i ][ $p ] - $graph [ $p ][ $i ]);

minCashFlowRec( $amount );

}

$graph = array ( array (0, 1000, 2000),

array (0, 0, 5000),

array (0, 0, 0));

minCashFlow( $graph );

?>

Javascript

<script>

var N = 3;

function getMin(arr)

{

var minInd = 0;

for (i = 1; i < N; i++)

if (arr[i] < arr[minInd])

minInd = i;

return minInd;

}

function getMax(arr)

{

var maxInd = 0;

for (i = 1; i < N; i++)

if (arr[i] > arr[maxInd])

maxInd = i;

return maxInd;

}

function minOf2(x , y)

{

return (x < y) ? x: y;

}

function minCashFlowRec(amount)

{

var mxCredit = getMax(amount), mxDebit = getMin(amount);

if (amount[mxCredit] == 0 && amount[mxDebit] == 0)

return ;

var min = minOf2(-amount[mxDebit], amount[mxCredit]);

amount[mxCredit] -= min;

amount[mxDebit] += min;

document.write( "<br>Person " + mxDebit + " pays " + min

+ " to " + "Person " + mxCredit);

minCashFlowRec(amount);

}

function minCashFlow(graph)

{

var amount=Array.from({length: N}, (_, i) => 0);

for (p = 0; p < N; p++)

for (i = 0; i < N; i++)

amount[p] += (graph[i][p] - graph[p][i]);

minCashFlowRec(amount);

}

var graph = [ [0, 1000, 2000],

[0, 0, 5000],

[0, 0, 0]];

minCashFlow(graph);

</script>

Output:

Person 1 pays 4000 to Person 2 Person 0 pays 3000 to Person 2

Algorithmic Paradigm: Greedy
Time Complexity: O(N²) where N is the number of persons.
This article is contributed by Gaurav. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Design a Program to Record Transaction Graphicly

Source: https://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/

Share this post