NINJA ATTACK
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

Question

NINJA ATTACK

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
1 <= 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

Accepted Answer

Step 1 : Calculate the XOR of two numbers.
Strp 2 : Count the number of set bits.

Accepted Answer

Sorting

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’is the size of the given array.

As we are using a set for making pairs that take O(N) space.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where ‘N’is the size of the given array.

As in the worst case, we have to travel our all combinations, and sorting takes O(N * log(N) ) time all other operations take O(N) time.

Java (SE 1.8)

/*

    Time complexity: O(N * Log(N) )

    Space complexity: O(N) 



    Where N represents the size of given array.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    private static int[] parent;



    static void makeSet() {



        for (int i = 0; i < parent.length; i++) {

            parent[i] = i;

        }

    }



    static int findSet(int a) {

        return (a == parent[a]) ? a : (parent[a] = findSet(parent[a]));

    }



    static void unionSet(int a, int b) {

        a = findSet(a);

        b = findSet(b);



        if (a != b) {

            parent[a] = b;

        }

    }



    static int calc(ArrayList a, ArrayList b) {

        Collections.sort(a);

        Collections.sort(b);



        int dis = 0, i = 0, j = 0, sz = a.size();



        while (i < sz && j < sz) {

            int x = a.get(i);

            int y = b.get(j);

            if (x == y) {

                dis += 1;

                i++;

                j++;

            } else if (x > y) {

                j++;

            } else {

                i++;

            }

        }



        return dis;

    }



    public static int ninjaAttack(ArrayList ninja, ArrayList enemies,

            ArrayList> allowedSwaps) {

        int n = ninja.size(), dis = 0;

        ArrayList> setWiseNinja = new ArrayList<>();

        ArrayList> setWiseEnemies = new ArrayList<>();



        for (int i = 0; i < n; i++) {

            setWiseEnemies.add(new ArrayList<>());

            setWiseNinja.add(new ArrayList<>());



        }

        parent = new int[n];

        makeSet();



        for (int i = 0; i < allowedSwaps.size(); i++) {

            unionSet(allowedSwaps.get(i).get(0), allowedSwaps.get(i).get(1));

        }



        // arrange the elements set wise

        for (int i = 0; i < n; i++) {

            int j = findSet(i);

            setWiseNinja.get(j).add(ninja.get(i));

            setWiseEnemies.get(j).add(enemies.get(i));

        }



        // go over to each set and compare

        for (int i = 0; i < n; i++) {

            dis += calc(setWiseNinja.get(i), setWiseEnemies.get(i));

        }



        return n - dis;

    }

}

Python (3.5)

'''



    Time complexity: O(N * log(N))

    Space complexity: O(N) 



    Where N represents the size of given array.

    

'''



def makeSet():

    global parent



    for i in range(len(parent)):

        parent[i] = i



def findSet(a):



    global parent

    if(a == parent[a]):

        return a

    else:

        parent[a] = findSet(parent[a])

        return parent[a]



def unionSet(a,  b):



    global parent

    a = findSet(a)

    b = findSet(b)

    if (a != b):

        parent[a] = b



def calc(a, b):



    a.sort()

    b.sort()

    dis = 0

    i = 0

    j = 0

    sz = len(a)



    while(i < sz and j < sz):

        if (a[i] == b[j]):

            dis += 1

            i += 1

            j += 1



        elif (a[i] > b[j]):

            j += 1



        else:

            i += 1



    return dis



def ninjaAttack(ninja,  enemies,  allowedSwaps):



    global parent



    n = len(ninja)

    parent = [0]*n



    dis = 0



    setWiseNinja = []

    setWiseEnemies = []

    for i in range(n):

        temp = []

        setWiseNinja.append(temp)

        temp = []

        setWiseEnemies.append(temp)



    makeSet()



    for s in allowedSwaps:

        unionSet(s[0], s[1])



    # Arrange the elements set wise.

    for i in range(n):



        j = findSet(i)

        setWiseNinja[j].append(ninja[i])

        setWiseEnemies[j].append(enemies[i])



    # Go over to each set and compare.

    for i in range(n):

        dis += calc(setWiseNinja[i], setWiseEnemies[i])



    return n - dis

C++ (g++ 5.4)

/*

    Time complexity: O(N * Log(N) )

    Space complexity: O(N) 



    Where N represents the size of given array.

*/



vector parent;



void makeSet()

{

    for (int i = 0; i < parent.size(); i++)

    {

        parent[i] = i;

    }

}



int findSet(int a)

{

    return (a == parent[a]) ? a : (parent[a] = findSet(parent[a]));

}



void unionSet(int a, int b)

{

    a = findSet(a), b = findSet(b);



    if (a != b)

    {

        parent[a] = b;

    }

}



int calc(vector &a, vector &b)

{

    sort(a.begin(), a.end());

    sort(b.begin(), b.end());

    int dis = 0, i = 0, j = 0, sz = a.size();



    while (i < sz && j < sz)

    {

        if (a[i] == b[j])

        {

            dis += 1;

            i++, j++;

        }

        else if (a[i] > b[j])

        {

            j++;

        }

        else

        {

            i++;

        }

    }



    return dis;

}



int ninjaAttack(vector ninja, vector enemies, vector> allowedSwaps)

{

    int n = ninja.size(), dis = 0;

    vector> setWiseNinja(n, vector()), setWiseEnemies(n, vector());

    parent.assign(n, 0);

    makeSet();



    for (auto s : allowedSwaps)

    {

        unionSet(s[0], s[1]);

    }



    // arrange the elements set wise

    for (int i = 0; i < n; i++)

    {

        int j = findSet(i);

        setWiseNinja[j].push_back(ninja[i]);

        setWiseEnemies[j].push_back(enemies[i]);

    }



    // go over to each set and compare

    for (int i = 0; i < n; i++)

    {

        dis += calc(setWiseNinja[i], setWiseEnemies[i]);

    }



    return n - dis;

}

Accepted Answer

HASHMAP

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the array.

As we are using a hashmap and also set for storing pairs which takes O(N) space.

Time Complexity: O(n)Explanation:

O((N), where ‘N’ is the size of the array.

As we are traversing our array only once.