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