You are not logged in. Please login at www.codechef.com to post your questions!

×

count all pairs with given XOR x in given array.

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

arpit728's gravatar image

1★arpit728
6831765
accept rate: 10%


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

link

answered 07 Dec '16, 10:17

nishant_coder's gravatar image

6★nishant_coder
795
accept rate: 20%

@nishant_coder

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

(07 Dec '16, 10:27) arpit7281★

Complexity is same. O(n).

(07 Dec '16, 10:34) nishant_coder6★

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

(07 Dec '16, 11:03) arpit7281★

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) nishant_coder6★

@nishant_coder

Thanks, I understood.

(07 Dec '16, 22:17) arpit7281★
Answer is hidden as author is suspended. Click here to view.

answered 30 Apr '17, 19:03

marshal_roxx's gravatar image

3★marshal_roxx
(suspended)
accept rate: 2%

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);

}

link

answered 29 Apr '17, 23:45

mr_gaurav's gravatar image

1★mr_gaurav
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×678
×303
×234
×141

question asked: 07 Dec '16, 09:35

question was seen: 2,899 times

last updated: 30 Apr '17, 19:03