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

1

i/p :
5
41 47 34 40 29

I didn’t get efficient approach for this problem.

2

could you share code/data structure used or algorithm ?
that would be much appreciated.
Else I have to assume that the sets and pairs are provided in a 2D array format.

3

I don’t know which algorithm is used but i am trying to use bit masking.
you can assume them as pairs

5

I’m a bit confused why one would use bitmasking to work with sets, hoping this is the problem to solve:

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

Lets tackle the problem using arrays and see whether it makes sense.

Consider 3 pairs input into a 2D array:
chef_code

Hence :

#include<stdio.h>
#define pairs 3                                  // number of pairs

int main()
{
int array[2][pairs]={{0,0,5},{21,0,6}};       //sample input
int result=0;
	
for(int i=0;i<pairs;i++)
{
	if(array[0][i]==0&&array[1][i]==0) result+=1;
}
printf("%d",result);

return 0;

}

1 Like
6

Awesome explanation by @sorb1997 . This should work, for smaller constraints. You might want to look into this entire topic to know new concepts.

1 Like