XOR
You are given an array ‘A’ of size ‘N’. Return true if an array can be divided into groups of pairs such that XOR of each pair is equal to 0.

A pair consists of two integers.

Example : Let the array be { 1, 2, 3, 4}

One of the ways to divide it into groups of pairs is { 1, 2 } and { 3, 4}.

Input format :

The first line contains a single integer ‘T’ representing the number of test cases.Then test cases follows : The first line of each test case contains an integer ‘N’. The second line of each test case contains ‘N’ space-separated integers denoting the elements of array ‘A’.

Output Format :

For each test case, print true if the array can be divided into groups of pairs with XOR 0, else print false. Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

XOR

You are given an array ‘A’ of size ‘N’. Return true if an array can be divided into groups of pairs such that XOR of each pair is equal to 0.

A pair consists of two integers.

Example : Let the array be { 1, 2, 3, 4}

One of the ways to divide it into groups of pairs is { 1, 2 } and { 3, 4}.

Input format :

The first line contains a single integer ‘T’ representing the number of test cases.Then test cases follows :

The first line of each test case contains an integer ‘N’.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of array ‘A’.

Output Format :

For each test case, print true if the array can be divided into groups of pairs with XOR 0, else print false.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N <= 10^5
1 <= A[i] <= 10^5

Time Limit : 1 sec

Accepted Answer

Optimal Approach

Approach :

We can see that if any element is present an odd number of times , then there will be no pair for it.

Since, to get XOR 0, we require to pair number ‘a’ with the same number.

Thus, we can just check if any element is present an odd number of times.

If yes, we return false.
Else, we return true.

Algorithm :

Maintain a HashMap.
Run a for loop from ‘i’ =1 to ‘i’ = ‘N’.
Inside this for loop :
- Put the element at this index in the map and increment its previous frequency.
Traverse the HashMap
- If any value is having odd frequency, return false.
Return true.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the given input.

We are maintaining a map , so overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O( N ), where ‘N’ is the given input.

Since we run a for loop from i=1 to i = N , the overall time complexity will be O(N)

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the given input.
*/

bool checkXORPairs(vector &arr, int n) {
    // An odd length array cannot be divided into pairs.
    if (n % 2 == 1)
    {
        return false;
    }

    // Create a frequency array to count occurrences.
    unordered_map umap;
    for (int i = 0; i < n; i++){
        if (umap.find(arr[i]) == umap.end())
        { 
            umap.insert(make_pair(arr[i], 0));
        }

        umap[arr[i]]++;
    }
    
    // Iterate through the key set.
    unordered_map:: iterator itr;
    for (itr = umap.begin(); itr != umap.end(); itr++){
        // Check if it has odd occurrences. 
        if(itr->second %2 == 1)
        {
            return false;
        }
    }

    return true;
}

Python (3.5)

"""
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the given input.
"""


def checkXORPairs(arr, n) :
    # An odd length array cannot be divided into pairs.
    if (n % 2 == 1):
    
        return False
    

    # Create a frequency array to count occurrences.
    
    umap={}
    for i in range(n):
        if (arr[i] not in umap.keys()):
        
            
            umap[arr[i]]=0
        

        umap[arr[i]]+=1
    
    
    # Iterate through the key set.
    
    for i in umap.keys():
        if(umap[i]%2==1):
            return False
   
    

    return True

Java (SE 1.8)

/*
	Time Complexity: O(N)
	Space Complexity: O(N)

	where 'N' is the given input.
*/

import java.util.HashMap;
import java.util.Iterator;

public class Solution {

    public static boolean checkXORPairs(int[] arr, int n) {
        // An odd length array cannot be divided into pairs.
        if (n % 2 == 1)
        {
        	return false;
        }

        // Create a frequency array to count occurrences.
        HashMap hm = new HashMap<>();
        for (int i = 0; i < n; i++){
            if (!hm.containsKey(arr[i]))
            {
            	hm.put(arr[i], 0);
            }

            hm.put(arr[i], hm.get(arr[i]) + 1);
        }

        Iterator itr = hm.keySet().iterator();
        while(itr.hasNext()){
            int element = itr.next();
            // Check if it has odd occurrences.
            if(hm.get(element)%2 == 1)
            {
            	return false;
            }
        }
        
        return true;
    }

}