New update is available. Click here to update.

Valid Pairing of Numbers

PROBLEM STATEMENT

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

Approach 1

Consider the pair ‘E’ and ‘E’ + 1(where ‘E’ is a particular even number in the given list) as the vertex in the graph. As the size of the given list/array is 2 * ‘N’ and so, the graph will contain ‘N’ vertices. Now, we have to connect the edges between the required vertices. There will be an edge between the two pairs of numbers (two vertices) in the given list if there present ‘E’ in a pair and ‘E’ + 1 in the other or vice-versa.

Now, we have to only find the number of disjoint sets of vertices (number of connected components) in the graph. The answer (minimum number of swaps) will be ‘N’ - the total number of connected components in the graph.

Reference: https://cp-algorithms.com/data_structures/disjoint_set_union.html

We are going to use an additional function named “FIND” that helps in finding the parent node of a child node. It takes the “PARENT” array and number/vertex ‘X’ as arguments and returns the parent of ‘X’.

int find(vector<int> &parent, int x)

Where “PARENT” is the array that holds all the parent nodes (or we can say root nodes of every connected component present in the graph) and ‘X’ is the vertex whose parent we are trying to find.

The steps are as follows:

In the “FIND” function
- If ‘X’ is equal to “PARENT[ X ]” then return ‘X’.
- Otherwise, we will do the path compression technique (see reference for further details). Make again a recursive call to the “FIND” function with arguments “PARENT” and “PARENT[ X ]”, and set the result obtained in “PARENT[ X ]”.
- Return “PARENT[ X ]”.
In the given function
- Make a vector named “PARENT” of size ‘N’ and set ‘i’ for every “i-th” position in this vector. We are doing this so as to make all vertices disconnected initially.
- Create a HashMap named “MP” that helps in mapping down two numbers in a particular pair.
- Now, Iterate through the given list/array “ARR”. (say, iterator = ‘i’)
  - Create a variable named “NUM” and store ARR[ i ] / 2.
  - Now, check whether it presents already in “MP”.
    - If, it is not present then do MP[ NUM ] = i / 2
    - Else, find the parent of MP[ NUM ] (vertex that includes “NUM”), store in “V1” and the parent of ‘i’ / 2 ( vertex that includes “ARR[ i ]”) in “V2” and then make parent of “V1” equals to “V2”.
    - All we are trying to do in the above step is making an edge between the required vertices (described in the approach section).
- Create a variable “CON_COMP” to store the number of connected components. Initialize it with 0.
- Iterate through “PARENT” and if find the parent of ‘i’ is equal to ‘i’ then increment “CON_COMP” by 1.
- Return ‘N’ - “CON_COMP”.

Try Problem

Approach 2

The basic idea of this approach is to just swap the numbers if they are not in a valid pairing and keep calculating the number of pairs that are not in a valid pairing i.e ‘E’ is not adjacent to ‘E’ + 1.

The steps are as follows:

Create a HashMap “MP” to store the number along with their position as they present in the given list/array.
Initially, make MP[ ARR[ i ] ] = ‘i’ for every number present in the given list/array. Here, ‘i’ indicates the position of a particular number.
Create a variable named “COUNT” to count the minimum number of swaps required to make every pair a valid pair.
Iterate through the “ARR”. (say, iterator = ‘i’)
- Create a variable named “NUM” that stores the other number that should be paired with ARR[ i ].
- Check if ARR[ i ] is even then store ARR[ i ] + 1 in “NUM”.
- Else store ARR[ i ] - 1 in “NUM”.
- Now, check if it is already in a valid pairing then just continue.
- Otherwise, swap ARR[ i + 1 ] with ARR[ MP[NUM] ] and change the position of ARR [ MP[NUM] ] in “MP”.
- Increment “COUNT” by 1.
Return “COUNT”.

Try Problem

Valid Pairing of Numbers

PROBLEM STATEMENT

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:

Note:

Input Format:

Output Format:

Note:

Constraints:

Approach 1

Approach 2

Interested in Coding Ninjas Flagship Courses?