You are given an array A of size N and an integer X.

Find the count of all the pairs (i,j) such that ((A_i \oplus A_j)\&X) = 0. Here \oplus and \& denote bitwise XOR and bitwise AND operations respectively.

EXPLANATION:

The given expression in the problem can be written as:

So in order to find the number of pair (i,j), we can construct a new array A' such that A'[i] = A[i] \&X, \forall i , 0 \leq i < n and then find the number of pairs (i,j) in this new array A' such that A'[i] = A'[j] which can be done easily using a hash map to store the frequency of each element in A'.

Assuming there are total N elements.
given: (Ai ^ Aj) & X = 0 â€” (1)

case 1: X = 0 ==> N * N
case 2: all Ai are zero ==> N * N
case 3: when X non zero and there are some elements in A that are not zero:
Idea: record the count of the elements having 0 common bits with X.
record the count of elements having 1 common bit with X.
â€¦
.
.
record the count of elements having all bits common with X.

Finally, return the total number of pairs.

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define int long long
void solve() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> arr(n, 0);
for (int i=0; i<n; ++i) {
cin >> arr[i];
}
int x; cin >> x;
int ans = 0;
vector<int> x_bit(32, 0);
vector<int> same_bit_count(32, 0);
for (int i=0; i<32; ++i) {
if ((x & (1LL << i))) {
x_bit[i]++;
}
}
for (int i=0; i<n; ++i) {
int v = 0;
for (int j=0; j<32; ++j) {
if ((arr[i] & (1LL << j)) != 0 && x_bit[j] != 0) {
v += 1;
}
}
same_bit_count[v]++; // stores total numbers having 'v' common bits with X.
}
// total pairs.
for (int i=0; i<32; ++i) {
ans += (same_bit_count[i] * same_bit_count[i]);
}
cout << ans << "\n";
}
return;
}
signed main() {
solve();
return 0;
}

I donâ€™t know that distributive property is also valid in bitwise operators. This makes the question so easy.
I was thinking about another solution i.e.,
if ((ai ^ aj) & x) == 0 then ai^aj can only be equal to y(y = x after reversing all its bits) or 0. Then I can find all the pairs whose xor is equal to y or 0 in O(N).
But this didnâ€™t work.
Can anyone please tell me what is wrong with this solution?

for (auto it : m)
{
ll curr = (it.second * it.second);
ans += curr;
}

shouldnâ€™t we write this statement only if the it.second> =2?
suppose a element exists that gives a value y= a[i]&x and it is the only element.
if we count it also, doesnâ€™t it mean we are considering the same i twice and making its pair?
for example in following test case :

1
4
1 2 3 1
1

2 & 1 = 0 and itâ€™s the only element which gives 0 as output. counting it will mean that we are making the pair (2,2).

I used recursion to solve this. didnâ€™t know the formula could be simplified like this.
In my solution, I check which bits are set in X, then to make the whole formula equal to 0, we need to make these bits into 0 and the operation is bitwise AND. we have to look for those pairs of Ai and Aj such that their xor for those positions where X bit is 1 becomes 0.
time complexity:
n = number of bits to represent X in binary
O(n)