Some N friends are there who have to Give and Take money from each other. We aim to minimize the number of operations ie Give and Take using C++.
There are N friends who went to a party at a hotel. Some of them had forgotten to carry their wallet so their other friends paid for them. After they return to their hostel, all the friends sat at a conference and will now decide who to pay what and who to receive what money. Now as a helper of the N friends Ramu wants to minimize the operations that they shall do to settle the amount between each of them.
So, Ramu thought of the idea of a Greedy Algorithm. He thought that he would settle the amount for each person and recur for the remaining persons. But Ramu is in a fix now. How would he pick the first person whose amount he wants to settle? He got an idea to calculate all the net Give and Take for all N friends and then he picks two of them with maximum and minimum net amount. He then settles the amount between them and removes them from the list and continues in this way until all the amount is settled.
Following the above approach, we can get the minimum number of operations needed to settle the amount between the friends.
We can find out more by looking at the following image:-
I have attached the code with this packet.
Submitted by Soumak Poddar (soumakpoddar)
Download packets of source code on Coders Packet