CFXORB Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Nikhil Kumar
Tester: Felipe Mota, Abhinav Sharma
Editorialist: Pratiyush Mishra

DIFFICULTY:

2080

PREREQUISITES:

Bitwise Operations

PROBLEM:

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:

((A_i \oplus A_j) \&X) = (A[i] \& X) \oplus (A[j] \& X)

Also we know that:

a \oplus b = 0 \implies a = b

Thus we get:

(A[i] \& X) \oplus (A[j] \& X) = 0 \implies (A[i] \& X) = (A[j] \& X)

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

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like
2

Can anyone tell what is wrong with this approach?

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;
}
3

Fails for this

1
2
4 10
6

Correct output is 2

1 Like
4

Thanks, @cubefreak777. I found the error.

5

why you are adding same_bit_count for every i [0,32]
if you think this can make pair then you are wrong because

x=10=1010
n=2
a[]={8,2}={1000,0010}
your code will print 4 but correct output is 2

1 Like
6

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?

Thanks in advance.

7

I didn’t think of this case. otherwise, I wouldn’t have tried to approach the problem this way.

8

My approach [constructive]
click here

x=1010110
our pairs is depend only on the set bits indexs
0,2,4,5 th is set in x

n=3
1101011
{1,0,0,1} // [0,2,4,5 th bits]

1110111
{1,1,1,1} // [0,2,4,5 th bits]

1100010
{1,0,0,1} // [0,2,4,5 th bits]

we can make pair with [1,3]
like this we count the freq of array of length max 32

ans+=freq*feq

9 
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).

10

I think my appoach is also similar to yours but I’m not able to debug. Can you help with this?
Here’s my WA link: CodeChef: Practical coding for everyone

11

i can be equal to j. So, it.second need not be at least 2.

12

oh,ok

13

sorry for late reply

You are considering only cases
pairing element where both bits are set
but there are more cases

suppose let say {all in binary}
x=1001
a=[1100,1111,1011,1010,1101,0101]

By your approach valid pairs are
{ [2,3] [2,5] [3,2] [3,5] [5,2] [5,3] + n pairs}

But there are more valid pairs
{[1,4][4,1]}

I hope it’s clear now

14

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)

solution here

15

I solved it without using the distributive property, also I don’t think we always can use distributive property for bitwise operations, is it always we can use it for AND ? or this is not always the case!?