fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <vector>
  4. #include <string>
  5. #include <tuple>
  6.  
  7. using namespace std;
  8.  
  9. struct Transaction {
  10.     string from;
  11.     string to;
  12.     int amount;
  13. };
  14.  
  15. // Greedy Settlement Approach
  16. vector<tuple<string, string, int>> settleBalances(const vector<Transaction>& transactions) {
  17.     unordered_map<string, int> balance;
  18.  
  19.     // Step 1: Compute net balances
  20.     for (const auto& tx : transactions) {
  21.         balance[tx.from] -= tx.amount;  // Payer loses money
  22.         balance[tx.to] += tx.amount;    // Receiver gains money
  23.     }
  24.  
  25.     // Step 2: Create lists of debtors and creditors
  26.     vector<pair<string, int>> debtors, creditors;
  27.     for (const auto& [person, bal] : balance) {
  28.         if (bal < 0) {
  29.             debtors.emplace_back(person, bal);  // owes money
  30.         } else if (bal > 0) {
  31.             creditors.emplace_back(person, bal);  // is owed money
  32.         }
  33.     }
  34.  
  35.     // Step 3: Match debtors to creditors
  36.     vector<tuple<string, string, int>> result;
  37.     int i = 0, j = 0;
  38.  
  39.     while (i < debtors.size() && j < creditors.size()) {
  40.         int amount = min(-debtors[i].second, creditors[j].second);
  41.  
  42.         result.emplace_back(debtors[i].first, creditors[j].first, amount);
  43.  
  44.         debtors[i].second += amount;
  45.         creditors[j].second -= amount;
  46.  
  47.         if (debtors[i].second == 0) ++i;
  48.         if (creditors[j].second == 0) ++j;
  49.     }
  50.  
  51.     return result;
  52. }
  53. int main() {
  54.     vector<Transaction> txns = {
  55.         {"A", "B", 10},
  56.         {"B", "C", 5},
  57.         {"C", "A", 5}
  58.     };
  59.  
  60.     auto result = settleBalances(txns);
  61.  
  62.     for (const auto& [from, to, amount] : result) {
  63.         cout << from << " pays " << to << " ₹" << amount << endl;
  64.     }
  65.  
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
stdout
copy 
A pays B ₹5
https://ideone.com/5PkOkq
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!