count all pairs with given XOR x in given array.

general
, , ,
1

Given an array A[] of size N and a number x. count all the pairs in array such that A[i]^A[j]=x.

DON’T PROPOSE THE SOLUTIONS WITH O(N^2) AND ALSO THE SOLUTION GIVEN ON GEEKSFORGEEKS

THIS IS THE SOLUTION PROVIDED BY CODEFORCES

Note that if then . Keep in numx the number of repetitions of number x. Now for each x, add to answer. Then divide answer by 2 (if X is 0, don’t).

Time complexity: O(n).

Corner case #1 : Some codes got WA when X is 0.

Corner case #2 : Some codes got RE because can be as large as max(x, y)·2.

I couldn’t understand this solution please explain this one or some other approach.

1 Like
2

BITWISE XOR has a property that xor exist in triples. for eg. if a^b=c then a^c=b and b^c=a… we can use this property of xor to find the state of dp! So ques is to find the no. of pairs (i,j) for which a[i]^a[j]=x. Since the value of a[i]<=10^5 we can store the occurences of each value a[i] in array (say b[]). We can initialize array b[] with 0 and increment b[a[i]] for i from 1 to n.
Now we will find the no. of occurences of a[i]^x and add it to the answer for i from 1 to n. (i.e. ans+=(b[a[i]^x] ),Now this answer will be the twice of the answer required (as pair (i,j) and (j,i) both are included in this answer). So we will divide the answer by two.
Note that the size of array b will be more than 200000 as the xor a[i]^x can be greater.
Corner case. When x=0.the pair (i,i) will also get included. (as val^val=0 for all val). So we will subtract n from the answer.
for reference …Here is my code! http://ideone.com/mFOahw

1 Like
3

@nishant_coder

Did you understand the codeforces solution I mentioned in the question. I think that’s even better.

4

Complexity is same. O(n).

5

@nishant_coder

Sorry, I couldn’t recognize in codeforces solution numx is an array.

Please explain when x=0 case in more detail, I couldn’t understand that part.

6

As we know that xor of a number with itself is zero . So in our answer, pair (i,i) will also be included (because a[i]^a[i]=0). So we need to subtract these pairs i.e. we have to subtract n from the answer.

7

@nishant_coder

Thanks, I understood.

8

#include<stdio.h>
int main()
{
int A[100],N,x,k,i,j, count=0;
printf(“enter the size of array {max100}”);
scanf("%d",&N);
printf(“enter the elements of array “);
for(i=0;i<N;i++)
{
scanf(”%d”,&A[i]);
}
printf(“enter the value of x=”);
scanf("%d",&x);

for(i=0;i<N;i++)
{
	for(j=i;j<N;j++)
	{
		k=A[i]*A[j];
		if(k==x)
		{
			count=count+1;
		}
	}
}
printf("\nthe number of possible pairs=%d",count);

}

9

make a hash set and check for element a[i]^x . if it is in that array , increment the count , else add the element to the hash set .

1 Like