# War of XORs | codechef solution

Chef is stuck at the following problem. Help him solve it!

Chef has a sequence of integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$. He should find the number of pairs $\left(�,�\right)$ such that $1\le �<�\le �$ and the bitwise XOR of ${�}_{�}$ and ${�}_{�}$ can be written as a sum of two (not necessarily different) prime numbers with the same parity (both odd or both even).

### Input

• The first line of the input contains a single integer $�$ denoting the number of test cases. The description of $�$ test cases follows.
• The first line of each test case contains a single integer $�$.
• The second line contains $�$ space-seprated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$.

### Output

For each test case, print a single line containing one integer — the number of valid pairs.

### Constraints

• $1\le �\le 10$
• $1\le �\le 1{0}^{5}$
• $1\le {�}_{�}\le 1{0}^{6}$ for each valid $�$

Subtask #1 (10 points): $1\le �\le 1{0}^{3}$

Subtask #2 (90 points): original constraints

### Sample 1:

Input
Output
1
5
2 4 8 1 3
3

### Explanation:

Example case 1: The three valid pairs are $\left(1,2\right)$$\left(1,3\right)$ and $\left(2,3\right)$. For example, ${�}_{1}\oplus {�}_{2}=2\oplus 4=6=3+3$.

Code(C++):-

#include <iostream>

using namespace std;

typedef long long ll;

const int M = 1000010;
ll t,n,x,e,o,s,a[M];

int main() {
cin >> t;
while (t--) {
cin >> n;
s = 0, e = 0, o = 0;
for (int i = 0; i < M; i++) a[i] = 0;
for (int i = 0; i < n; i++) {
cin >> x;
a[x]++;
if (x%2) o++;
else e++;
}
for (int i = 1; i < M-4;i++) s += a[i]*((i%2?o:e)-a[i]-a[i^2]);
cout << s/2 << endl;
}
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
long o,c,y;
while(t-->0)
{
int a[]=new int[1000003];
o=0;c=0;y=0;max=0;
for(int i=0;i<n;i++)
{
x=Integer.parseInt(s[i]);
a[x]++;
if(x>max)
max=x;
if(x==1)
{
o++;
y+=(o-a[x]-a[x+2]);
}
else if(x%2==0)
{
c++;
y+=(c-a[x]-a[x+2]-a[x-2]);
}
else
{
o++;
y+=(o-a[x]-a[x+2]-a[x-2]);
}
}

for(int i=2;i<max;i+=4)
y+=a[i]*a[i+2]+a[i+1]*a[i+3];
System.out.println(y);
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-