Settle Debt

Hard
0/120
Average time to solve is 20m
15 upvotes
Asked in companies
eBayUberGoldman Sachs

Problem statement

A group of friends went on a trip and sometimes lent each other money. Each transaction among them is represented by the tuple (X, Y, Z) which means person ‘X’ gave person ‘Y’ $Z. Given a list of ‘N’ transactions between a group of friends, return the minimum number of transactions required to settle the debt.

Example:

Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. Assuming   Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transaction can be represented as [[0, 1, 10], [2, 0, 5]].So here the minimum number of transactions to settle the debt is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains one integer ‘N’ where ‘N’ denotes the number of transactions between a group of friends.

Then N lines contain three space-separated integers ‘X’, ‘Y’ and ‘Z’ which denotes person X gave person Y $Z in the form of N x 3 ‘ARR’ matrix where the first column represents lender, the second column represents receiver and the last column represents the money given.
Output format: 
For each test case, print a single line containing a single integer denoting the minimum number of transactions required to settle the debt.

The output for each test case will be printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.

A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2, or we could also have the persons 0, 2, 6.
Constraints: 
1 <= T <= 10
1 <= N <= 9

Where ‘T’ represents the number of test cases, and ‘N’ represents the number of transactions among the friends.

Time Limit: 1 sec.
Sample Input 1:
1
2
0 1 10
2 0 5
Sample Output 1:
2
Explanation 1:
For the first test case, 
Person-0 gave person-1 $10.
Person-2 gave person-0 $5.

Therefore, Two transactions are needed. One way to settle the debt is person-1 pays person-0 and person-2 $5 each.
Sample Input 2:
1
4
0 1 10
1 0 1
1 2 5
2 0 5
Sample Output 2:
1
Explanation 2:
For the first test case, 
Person-0 gave person-1 $10.
Person-1 gave person-0 $1.
Person-1 gave person-2 $5.
Person-2 gave person-0 $5.

Therefore, only 1 transaction is needed. Person-1 only needs to give person-0 $4, and all debt is settled.


Hints:
Think of a recursive solution.
Approaches (1)
Settle Debt

Approach:

  • The idea is to use a hash table to create a mapping between each person and their account. If the account is positive, it means that others owe you money; if the account is negative, it means that you owe others money. For each bill, the person in front subtracts the amount of money from the hash table, and the person behind adds the amount of money to the hash table. In this way, each of us has an account, and the next thing we have to do is to merge the accounts to see how many remittances are required at least.
  • Then we count the number of people whose account value is not 0, because if it is 0, it means that you neither owe money to others nor do others owe you money. If it is not 0, we put the amount of money into another array and then call a recursive function on that newly formed array.
  • In the recursive function, start from the first non-zero value and try to settle up the rest and use backtracking to get global minimum number of transactions.
  • We could settle only when currentAccount * nextAccount < 0 and we can perform one transaction to settle them up.

 

Algorithm:

  • Iterate through the ‘Arr’ matrix to get the balance of each account. Use HashMap ‘Account’ to store the initial debts of each person, negative means the person sends money to others, positive means the person gets money from others.
  • Here ‘debt’ represents the balances of each person.
  • Now iterate through the map ‘Account’ and consider only those people with debts(either positive or negative) and store them in a vector ‘Debt’.
  • Now call the recursive function ‘settleDebtHelper’.
  • Recursive function : settleDebtHelper(Debt , startIndex), where startIndex = 0 initially.
  • In the recursive function, we initialize the result ‘minimumTransactionCount’ to the integer maximum, then we skip the account with debt 0.
  • For the current ‘startIndex’ we have to select an index ‘i’ (startIndex+1 <= i < n) such that it satisfies   Debt[startIndex] * Debt[i] < 0.Then you can use it to clear Debt[startindex] to 0 i.e Debt[i] += Debt[startIndex].
  • Then continue to the next recursive call: Helper(startindex+1, Debt) + 1.
  • Update ‘minimumTransactionCount’ = min(minimumTransactionCount, Helper(starindex+1, Debt) + 1).
  • Then backtrack, select other index ‘i’ to clear Debt[start_idx] to 0, i.e Debt[i] -= Debt[startIndex].
  • Then finally return ‘minimumTransactionCount’ as the answer.
Time Complexity

O(N!), where N is the number of transactions.

 

Storing the initial debts of each person on the map will take O(N) time. Now traversing the map and storing all non-zero values in an array will take O(N) time. Calling the recursive function N times and performing backtracking along with it will take O(N!) time. Thus, the total time complexity will be O(N + N + N!) = O(N!).

Space Complexity

O(N), where ‘N’ is the number of Transactions

 

O(N) extra space is required for the Hashmap. Also, O(N) extra space is required to build the temporary array. Hence, the overall space complexity is O(N). 

Code Solution
(100% EXP penalty)
Settle Debt
Full screen
Console