PROBLEM LINK:Setter Priyanshi Gupta DIFFICULTY:EASY PREREQUISITES:Goldbach's Conjecture , Frequency array concept, Properties of XOR. PROBLEM:Given an array $A$ of $N$ numbers, we need to tell number of pairs of indices $(i,j)$ such that  QUICKEXPLANATION:Key to AC Deducing $2$ facts Deducing above $2$ was was the main turning point, and difference between a quick AC and complete cluelessness. Quick Explanation Focus on what the question says. It first says that, $A_i \oplus A_j$ must be representable as a sum of prime numbers of same parity. Its basic math that adding two numbers of same parity results in a sum of even parity ($i.e.$ $Odd+Odd=Even.$ $Even+Even=Even$). Also, the same rule holds for XOR. Appplying Goldbach's conjecture, the question reduces to find how many pairs $(i,j)$ exist such that For XOR being even, we check only among pairs with same parity. For XOR being greater than $2$, we first find number of all possible even XOR values, and then reduce count of XORs with value $2$ and $0$. This can be done easily via frequency array. EXPLANATION:The explanation will have a single section explaining editorialist's solution. Some proofs are left as in exercise to reader  their answers can be found in my bonus corner at the end of editorial. Try to read the editorial in a way to capture the thought process going in mind of a coder, because often we all know and are aware of things but fail at application in correct form. I assume you are thorough with basic properties of XOR. Please read them under prerequisites if its not the case! Editorialist's Solution Lets first discuss the solution of first subtask for formality. The idea of first subtask is to use $2$ nested loops, and try out all the possible $\frac{N*(N1)}{2}$ values of $i$ and $j$. If their XOR is even and greater than $2$, add $1$ to answer. Now, before moving towards the full solution, grasp the $3$ rules I say below. If having trouble, try to prove them or check out proofs in the bonus corner below. Then, proceed once you have proper clarity about those. 1. Only the rightmost bit (i.e. Leastsignificant bit or LSB) determines whether a number is odd or even. With above $3$, we can get a hint of implementation in mind. We need a count of numbers which are $odd$, and which are $even$ (so that their XOR is always even). After that, we have to check that the equivalent XOR is greater than $2$. If it is, then by Goldbach's conjecture, any even number greater than $2$ satisfies our condition of being a sum of $2$ primes of same parity. Now, this part is where most of contestants face problem  usually because they never did a similar problem before. Newbies get overwhelmed by "Ok its easy to make sure that XOR is even, but how do I assure that its greater than $2$ and include only proper indices in my answer?!" The answer is simple, dont! The proper methodology is to, first find the answer including repetitions and pairs with XOR $\le 2$ as well, and later subtract irrelevant ones from answer. (You can find a note about it in point $3.$ of my corner.) Making sure that XOR is $>2$ on the run is difficult. Instead, first just count how many pairs $(i,j)$ are there such that $A_i \oplus A_j$ is even. That is easy, right? Make it easier, for now, forget about restriction of $1 \le i < j \le N$, just find any pair $(i,j)$ such that $1 \le i,j \le N$. Any pair will do, no constraints on $i$ and $j$. Can you do that, if you are given the array $A$ and know how many numbers in it are $odd$ and how many numbers are $even$? (Check out tab below to see how if cannot). Now, we have the answer in crude form, what we have to do is to account for repetition of pairs (we counted $(2,1)$ and $(1,2)$ differently, which makes our answer twice the expected one), which can be easily done by halving the answer in the end. First, we have to take care of cases when XOR comes out to be $2$ or $0$ (i.e. even number $\le 2$). This is also simple! For this, maintain a frequency array, and now count how many times each number occurs. Now, think to yourself, for every element in array $A_i$, how many choices do I have to choose $j$ such that $1 \le i,j \le N$ and $A_i \oplus A_j=2$ ? Lets use $b$ to represent all numbers such that $b \oplus A_i=2$. We find that $b=A_i \oplus 2$. (Proof given in tab below). Hence, all we have to do is to subtract the count of numbers with value $A_i \oplus 2$ to account for numbers having XOR=$2$!! Similarly, to account for numbers with XOR $0$, we think of how many choices do I have to choose pairs $(i,j)$ under same conditions (as above) such that $A_i \oplus A_j=0$. It is very easy to see that, if we use $b$ to represent choices of numbers such $A_i \oplus b=0$, then this will imply that $b= A_i$. Hence, we simply reduce frequency of $A_i$ from our crude answer. (Check out above proof and try to follow exact guidelines to derive this, if in confusion how we concluded this. The steps to be followed are exact same!). In the end, as I mentioned above, after accounting for XORS resulting in $2$ and $0$, we simply halve the answer to get the final answer to print :) . As an exercise, try to write down an implementation of above idea in pen and paper. A code to compare your implementation with is given below as answer One warning though, make sure to declare your frequency array larger than size $1000001$ so that you dont get out of bounds when checking for count of $A_i \oplus 2$ SOLUTIONThe respective codes are also pasted in tabs below in case the links do not work. This is for convenience of readers, so that they can copy paste it to whichever IDE or editor they are comfortable reading it in and immediately have access to the codes. :) Author's solution can be found here. $Time$ $Complexity=O(N)$ CHEF VIJJU'S CORNER :D1. Proof Only LSB determines pairty. 2. XOR of same parity is always even. 3. LoEE 4. Related problems  The only reason newbies are not able to solve problems on frequency array topic is because of lack of practice. Practice these problems till the process becomes completely mechanical and intuitive for you. :)
asked 07 Sep '18, 11:25

What I did in this problem is :> Split input in two arrays1) odd > Divide each number by 4 (removing last two bits)why? Now for both arrays (odd and even )Count freq of each element in array of size $10^6/4 +1 $ (range/4 as I have divided each value by 4)Do : $ans= { n \choose 2 }$ (n is size of each array)Then: $ans= \sum_{k=0}^{k=10^6/4} { freq(k) \choose 2}$That is nothing but, all possible pairs ${ n \choose 2 }$  pairs whose xor is 0 or 2 ( $ { freq(k) \choose 2}$ for each k )Simple Implementation in c++ can be found HEREanswered 17 Sep '18, 22:58

For me, I first created a frequency array, and also split the input array into two arrays:
I then sorted the two arrays(I will latter on apply binary search), and performed the following steps:
There were a few observations which I made, leading to my decision to apply binary search:
So the way I calculated the pairs whose XOR is 2 was by applying binary search separately on each sorted array, starting from the first number a[1] in the array, I would then search for either (a + 2) or (a  2) depending on the above observations, and then marking all indexes from (a + 2) onwards or (a  2) onwards as seen, so that those indexes wouldn't be latter on visited. Here's my solution https://www.codechef.com/viewsolution/20133014 answered 18 Sep '18, 16:09

how can i reduce the time required for this execution..?
answered 18 Sep '18, 11:12
Firstly, Python has an xor operation: a^b. No need to code your own. Then read the editorial and i_return's answer.
(18 Sep '18, 11:53)

Goldbach's conjecture was proved upto 4*10e18 :) answered 18 Sep '18, 11:21

https://www.codechef.com/viewsolution/20237335 In my implementation, instead of halving the value at the end. I have decremented the frequency and odd or even before each iteration. So, can anyone point out which case did i miss. Thanks in Advance
link
This answer is marked "community wiki".
answered 19 Sep '18, 16:18

I got WA for the following code: https://www.codechef.com/viewsolution/20244104 Can someone please suggest me a testcase for which this code fails? answered 20 Sep '18, 00:34

for better clarity one can use structures, as i have used. check out thislink text https://www.codechef.com/viewsolution/20240933code and u will understand everything. answered 20 Sep '18, 14:25

int n = scn.nextInt(); long[] arr = new long[n];
link
This answer is marked "community wiki".
answered 20 Sep '18, 19:00

https://ide.codingblocks.com/#/s/28157 this fails for the last test case.can anyone help answered 25 Sep '18, 00:49

IN RESPONSE TO:https://discuss.codechef.com/questions/134985/xoriereditorial/135714 @ayush3890 Hi , I think we both have used similar approach , you can have a look at my code. If it helps. https://www.codechef.com/viewsolution/20337606 answered 26 Sep '18, 16:12

Minor typo  "Goldbach", not "Goldback" (in the prerequisites)