Last Updated: 3 Apr, 2021
NINJA ATTACK
Moderate
Asked in company
Ninja has built his team of ninjas to fight with the enemies in his city. Ninja made a plan of attacking all his enemies. In his team, every ninja has his own range of hitting and they had secretly got the hitting range of their enemies as well. So Ninja allowed some swaps between his ninjas so that they can minimize the hamming distance that is the number of positions where the hitting range of enemies and ninjas are different.
Your task is to write a code that can minimize the hamming distance. You are being provided with two arrays ‘ninja’ and ‘enemies’ both of the same size and an array ‘allowedSwaps’ where each allowedSwaps[i] = [ ai, bi ] indicates that you are allowed to swap the elements at index ai and index bi.
The Hamming distance of two arrays of the same length, ninja, and enemies, is the number of positions where the elements are different.
Example :
Consider the case ‘ninja’array is [ 1, 2, 3, 4 ], ‘enemies’array is [ 2, 1, 4, 5 ] and ‘allowedSwaps’ are = [ [ 0, 1 ], [ 2, 3 ] ] so after swapping in best manner according to ‘allowedSwaps’ our ‘ninja’ array becomes [ 2, 1, 4, 3 ]. So minimum Hamming distance is ‘1’ as now there is only one different element as compared to ‘ninja’ and ‘enemies’ array index.
Note :
1. You are allowed to do as many swap operations on the ‘ninja’ array as you want but according to the ‘allowedSwap’ array.
2. You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Input Format :
The first line of input contains a ‘T’ number of test cases.
The first line of each test case contains an integer ‘n’, which represents the size of the array ‘ninja’ and ‘enemies’.
The second line of each test case contains the ‘n’ space-separated integer of array ‘ninja’.
The third line of each test case contains the ‘n’ space-separated integer of array ‘enemies’.
The fourth line of each test case contains an integer ‘m’ denoting the number of rows in array ‘allowedSwap’. Then, ‘m’ lines follow.
Each line contains two space-separated integers denoting the array values.
Output Format :
For each test case, return the minimum hamming distance of the ‘ninja’ and ‘enemies’ array.
Constraints :
1 <= T <= 100
1 <= N <= 10^3
0 <= ninja[i], enemies[i] < 10^5
0 <= allowedSwaps[i] <=10^5
Where ‘T’ represents the number of test cases, ‘N’ represents the size of the ‘ninja’ and ‘enemies’ array and ninja[i], enemies[i], and allowedSwaps[i] represents the element in the array.
Time Limit: 1 second
Approaches
The logic used here is, for ex-
‘arr = [1, 2, 3, 4]’
If swap(1, 2) allowed, and swap(1, 4) allowed and we are allowed to do any number of swaps,
then 1, 2, 4 can be rearranged into any possible combination, it forms a SET.
We only need to compare the values of the ‘2’ SET that we find for each array.
- First, we arrange the elements set wise of ninja and enemies in the form of pairs.
- Now we traverse our whole set and try to compare each set of elements by making all possible combinations by swapping elements.
- Now we sort both our set of ninja array and enemies array and compare them.
- If elements in one array are equal to another array we increase our variable.
- Then in the last, we return the total number of elements subtract from our variable as our answer.
The idea here is to use union and try to find all the connected groups (allowedSwaps). In each group find the number of elements that appeared in the ninja array but not in the enemies array.
The logic used here is, for ex-
arr = [1, 2, 3, 4]
If swap(1, 2) allowed, and swap(1, 4) allowed and we are allowed to do any number of swaps,
then 1, 2, 4 can be rearranged into any possible combination, it forms a SET.
We only need to compare the values of the ‘2’ SET that we find for each array.
- So first we implement the data structure union ‘unionFind’ on our allowedSwaps array to store all the connected groups.
- Now we use a hashmap based on ‘unionFind’ and store the key-value pair in the way that key represents the root value of every separate group and value is the member which is the index in source and target array in each group.
- Now we go through our hashmap and note down how many elements appear in the ninja array and not in the enemies array for every group.
- In the last, we simply return our minimum answer to the group.