Problem Link : Practice
Author : Ankur Pandey
**Editorialist : ** Shivesh Tiwari
Difficulty
Easy
Explanation
In this question, we’re given an array of n elements, and we’ve to count number of pairs of elements ai and aj such that i<j and ai&aj >= ai⊕aj, & denotes bitwise AND operation, ⊕ denotes bitwise XOR operation.
Now let us see when will ai&aj >= ai⊕aj satisfies.
let ai = 4, aj = 3
0100 & 0011 = 0000
0100 ⊕ 0011 = 0111
this doesn’t satisfies our condition.
let us take another example, ai = 4, aj = 7
0100 & 0111 = 0100
0100 ⊕ 0111 = 0011
this time the condition is satisfied.
We can observe that the condition satisfies only when their (ai and aj) most significant bit is on same index.
So we’ll count the numbers whos MSB is same, we’ll use map for this.
Since their is one more condition, i < j, so for this also, let us take an example.
a[] = {4, 7, 6, 5}
MSB of 4, 7, 6 and 5 is same, hence they will make pairs.
4 can make pair with all 7, 6 and 5
7 can make pair with both 6 and 5
6 can make pair only with 5
5 can’t make any pair
total pairs = 3+2+1 = 6. i.e 4*(4-1) / 2;
ans = (pair*(pairs-1))/2 for that specific pair.
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll getMSB(ll n) {
n|=(n>>1);
n|=(n>>2);
n|=(n>>4);
n|=(n>>8);
n|=(n>>16);
return n - (n>>1);
}
void code(){
ll n; cin>>n;
map<ll, ll> mp;
for(ll i=0; i<n; i++) {
ll a; cin>>a;
ll MSB = getMSB(a);
mp[MSB]++;
}
ll ans = 0;
for(auto i: mp) {
ll cnt = (i.second * (i.second-1))/2;
ans += cnt;
}
cout<<ans<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
int t=1;
cin>>t;
while(t--) {
code();
}
}