This question was asked in a hiring challenge. I have tried to do ascending sort based rightmost greater bit and then in each query do binary search for each bit starting from rightmost bit but I can't get that idea working even on paper. Can someone help me out with this problem as I am stuck? Any help would be greatly appreciated.

**Problem statement**

Moin Akhtar wants to come to Hackerland for his next harmonium performance. So, you decided to check how good he is at the harmonium. Moin's harmonium has N keys and each key has a number written on it. You asked him Q queries in each query you gave him a number X. He has to tell is there any key available in the harmonium such that bitwise and (&) of X and that key comes out to be 0.

**Input Format:**

the First Line contains an integer N denoting the number of keys in the harmonium

Second-line contains an array Key of size N denoting the value written on each key of the harmonium

Third-line Contains an integer Q denoting the number of queries.

Each of the next Q lines contains an integer X (described in the problem statement.)

**OUTPUT FORMAT**

For each Query, Print "Yes" or "Not in a new line, passed fit whether there is a key such that Key_j & X = 0

**Constraints**

1<=N,Q,X<=10^5

1<=Key_i<=10^5

**Sample Input**

3

1 2 3

5

1

2

3

4

5

**Sample Output**

Yes

Yes

No

Yes

Yes

Lets say that there is only 17 bits in number (10^6 > 2^17 > 10^5). Now for each key: key[i] = !key[i]. Now the query is: is there such key that key[j]&X==X? lets calculate that for each number from 2^17 to 0. Let gist be bool array with size of 2^17 + 1. for every key we: gist[key[i]] = 1; now:

(^ is power of) now for each query we just check if qist[x] == 1. and if it is true than answer is Yes, otherwise No

Thank You!

Your explanation seems really interesting but confusing, could you elaborate a little on what is happening in the nested for loop exactly?

The key idea is that if complement of a number x exists in the array, let's call it a[i] here. Now if we flip any of the set bit of x, let's call it x' then a[i] would be a complement of x' too. So, for each element we first find the maximum number of which that element is a complement (i.e. 2^(No of bits)-element) and then add those numbers too which can be obtained by flipping one or more set bits of 2^(No of bits)-element.

can anybody share the link of this question? my solution in python : https://onlinegdb.com/nl8If3Ah1

Can you explain your solution a bit?

I am not good in explaining, but will give a try.

My idea is suppose x = (010110) base2, then (_0_00_) base2 should be present in the original array (here _ can either be 1 or 0 because 0&1 = 0&0 = 0).

I have initialized a set named

storewhich will contain lists.Now for each key in the original array we repeat the below step:

we convert key[i] into 17-bit binary and store all the indices whose bit is 0. for example if key[i] = 10 (0000....1010)base2,

zero_bitswill be [0,2,4,5,6,7,....15,16]. now using recursion we produce all the combinations ofzero_bitsi.e. [], [0], [2], [4],... [0,2], [0,4], [0,5],.... [2,4], [2,5],.... [0,2,4],.... [0,2,4,5,6,...16]. Then add all these lists instore.Notethat we will not repeat the recursion if it is already present instore.Then for each query we have to convert query[i] into 17-bit binary and store all the indices whose bit is 1. For example, query[i]=5 (0000...0101)base2, then

one_bitswill be [0,2].Finally we have to check if

one_bitsis present instoreor not. If it is present, then answer is 'Yes', else 'No'.