New update is available. Click here to update.

Last Updated: 12 Mar, 2021

Difficulty: Hard

```
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.
```

```
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.
```

```
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.
```

```
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.
```

```
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.
```

SIMILAR PROBLEMS

The Food Inspector

Posted: 31 Jul, 2022

Difficulty: Easy

LRU Cache

Posted: 10 Sep, 2022

Difficulty: Moderate

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

8-Queen Problem

Posted: 19 Dec, 2022

Difficulty: Easy

Popular Interview Problems: