New update is available. Click here to update.

Valid Pairing of Numbers

Posted: 26 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are provided with a list of numbers from ‘0’ to (2 * ’N’ - 1). You have to find the minimum number of swaps needed to make every even number ‘E’ (present in the list) adjacent to (‘E’ + 1).

For Example:
List = [3, 0, 2, 1]

We have to make ‘0’ adjacent to ‘1’ and ‘2’ to ‘3’. And, to achieve this we can swap ‘0’ with ‘2’.

New list = [3, 2, 0, 1].

Therefore, the answer (minimum number of swaps) is equal to 1.
Note:
There will be only distinct numbers present in the given list.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ such that the size of the list is 2 * ‘N’.

The second line of each test case will contain 2 * ‘N’ integers separated by a single space that represents the elements/numbers present in the list initially.
Output Format:
For each test case, print the minimum number of swaps possible to make every even number ‘E’ adjacent to (‘E’ + 1).

Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 100
0 <= ARR[ i ] < 2 * N

Time limit: 1 sec