XOR Pairs

Easy
0/40
profile
Contributed by
5 upvotes
Asked in company
HashedIn

Problem statement

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}.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
6 4 6 4
3
1 3 2
Sample Output 1:
true
false
Explanation For Sample Input 1 :
For the first test case, we can divide the array A into 2 groups as { 4, 4} and { 6, 6} each with XOR 0. Hence, we print true. 

For the second test case, we have, ‘N’ = 3.
Let us try to pair 1 with 2, then XOR = 3.
Let us try to pair 1 with 3, then XOR = 2.
Since, there is no pair for 1, we print false.
Sample Input 2 :
2
5
1 4 5 5 4
6
4 9 4 9 5 5
Sample Output 2 :
false
true
Hint

Hint : Does frequency of an integer determine the answer.

Approaches (1)
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.
Time Complexity

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)

Space Complexity

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

 

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

Code Solution
(100% EXP penalty)
XOR Pairs
Full screen
Console