Perfect pair question:Find the number of pairs (a,b) in given set of n integers such that (a&b)=0

#1

quest link: https://hack.codingblocks.com/app/practice/5/995/problem
#include
using namespace std;

void PairZeroSum(long long int *a,int n){
int count =0;
for(int i=0;i<n;i++){
// count =0;
for(int j=i+1;j<n;j++){
if((a[j] & a[i]) == 0){
count=count+1;
//cout<<"("<<a[i]<<","<<a[j]<<")"<<endl;
}
// cout<<"("<<a[i]<<","<<a[j]<<")"<<endl;

	}
  }
   cout<<count<<endl;

}
int main () {
int n;
cin>>n;
long long int a[100005];

for(int i=0;i<n;i++){
	cin>>a[i];
}

PairZeroSum(a,n);

return 0;

}

#2

@Aditikumari hey you have used simple brute force method ,which will not satisfy,use this approach:
An efficient approach is to use Sum over Subsets Dynamic Programming method and count the number of ordered pairs. In the SOS DP we find out the pairs whose bitwise & returned 0. Here we need to count the number of pairs.

Some key observations are the constraints, the maximum that an array element can be is 104. Calculating the mask up to (1<<15) will give us our answer. Use hashing to count the occurrence of every element. If the last bit is OFF, then relating to SOS dp, we will have a base case since there is only one possibility of OFF bit.

dp[mask][0] = freq(mask)

If the last bit is set ON, then we will have the base case as:

dp[mask][0] = freq(mask) + freq(mask^1)

We add freq(mask^1) to add the other possibility of OFF bit.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.