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. asked 07 Dec '16, 09:35

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 answered 07 Dec '16, 10:17
Did you understand the codeforces solution I mentioned in the question. I think that's even better.
(07 Dec '16, 10:27)
Complexity is same. O(n).
(07 Dec '16, 10:34)
Sorry, I couldn't recognize in codeforces solution num_{x} is an array. Please explain when x=0 case in more detail, I couldn't understand that part.
(07 Dec '16, 11:03)
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.
(07 Dec '16, 21:20)
Thanks, I understood.
(07 Dec '16, 22:17)

Answer is hidden as author is suspended. Click here to view.
answered 30 Apr '17, 19:03

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);
} answered 29 Apr '17, 23:45
