Finding number of pairs with a certain XOR value

Reading time: 25 minutes | Coding time: 5 minutes

In this article, we are going to find the number of pairs in an unsorted array, whose XOR values matches with our target value (say K). Using our efficient approach (with Hash map), we can solve this in O(N) time complexity while the brute force approach takes O(N^2) time complexity.

The key to solve this problem is that A xor B = K => A xor K = B.

For example:

array = {3, 6, 8, 10, 15, 50},  K=5

output = 2

Explanation: (3^6)=5 and (10^15) = 5

xor(^):

The xor operation or the exclusive-or operation gives 0 as output when the inputs are same and 1 as output when the inputs are different.

The idea is that if a and b are different, then output is 1 or else, it is 0.

For example:

2^3 = 1
Here above we first convert 2 and 3 to their binary equivalents and then apply the xor operation in accordance to the truth table.

Brute force O(N^2)

We can actually solve this by iterating over each element and then finding its xor with all other elements and try to find the required xor. This process would take O(N^2) complexity.

pseudo code:

take an array a[]
input the elements
start the nested for loop:

for(i=0;i<=size-1;i++)
{   
    for(j=i+1;j<=size-1;j++)
    {
        //now we check for the condition that finds the required pair
        if(if (a[j]^a[i]== x) 
                c++;
    }  // increment to count the number of suitable pairs
}

Code implementation:

#include<bits/stdc++.h> 

using namespace std; 
int pair_calc(int a[], int n, int x) 
{ 
	int c=0; 
	
	for (int i=0; i<n ; i++) 
	{  
          for(int j=i+1;j<n;j++)
          {	
              if (a[j]^a[i]== x) 
                    c++;
          }
     } 
	return c; 
} 

int main() 
{   
    int a[100];
    int n;
    cin>>n;
    cout<<"enter the array"<<endl;
    for(int i=0;i<n;i++)
    {
    cin>>a[i];
    }
	int x ;
    cin>>x;
    
	cout << "The result is = "
		<< Pair_calc(a, n, x); 
	return 0; 
} 

Complexity:

Time complexity: O(N^2)

Hashing solution O(N)

If a[i]^a[j]=x then it is always true that a[i]^x = a[j].

In this solution we are going to use Unordered map to store the elements a[i] of the array, and with each entry we check if x^a[i] exists in the map. If it does then we have got a favorable case and hence we increase the output by 1. But if doesn't find the match then we simply insert the value like we always do.

Pseudo code:

set the counter as 0.
create an unordered_map "s".
No for each arr[i] in arr[]
     1.If x ^ arr[i] is in "s", then increase counter by 1.
     2. Insert arr[i] into the map "s".
     3. return counter.

Code implementation:

#include<bits/stdc++.h> 

using namespace std; 
int pair_calc(int a[], int n, int x) 
{    unordered_map<int,int> s;
	int c=0; 
	

	for (int i=0; i<n ; i++) 
	{  
    
        //in case there is an element with XOR equals to x^arr[i], that means 
        // there exist an element such that the 
        // XOR of element with arr[i] is equal to 
        // x, then increment counter. 
		if (s.find(a[i]^x)!= a.end()) 
			c += s[a[i]^x]; 
            
            s[a[i]]++;
	} 
	return c; 
} 

int main() 
{   
    int a[100];
    int n;
    cin>>n;
    cout<<"enter the array"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
	int x ;
    cin>>x;
    
	cout << "The result is = "
		<< Pair_calc(a, n, x); 
	return 0; 
} 

Example:

Input : arr[] = {25, 43, 10, 15, 78, 26}, x = 5
Output : 1

Explanation : (10 ^ 15) = 5

In the above example. we can consider the array arr[].

Now for each input in the array we scan for the map. At first each element is inputted because the map would be empty.Now if apparently we start finding the pairs we need then we just increment the pair so found.

Here till the element 10, we only insert the elements into the map. And then when we encounter 15, we find 15^5 and we find the match as 10. so it takes o(1) for the map to find the match, and for n elements we are going to get a complexity of O(n).

Complexity:

O(N).

This method of using maps also gets rid of the problem of duplication of elements. So hence give us a clear method to solve the problem.Otherwise this problem could also be solved with the help of sets but hen duplication of elements would have become a real issue.