Bammmmm's blog

Help required for this problem.
By Bammmmm, history, 3 years ago, In English

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:

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

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

  3. 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

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

for key : keys
    gist[key] = 1
for i = 2^17...0
    if (gist[i])
        for j = 0...17
            if (i & 2^j)
                gist[i - 2^j] = 1

(^ 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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    #include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n; cin >> n;
    vector<int> keys(n);
    for (int i = 0; i < n; ++i)
        cin >> keys[i];
    
    vector<int> pw(19, 1);
    for (int i = 0; i < 19; ++i)
        pw[i + 1] = pw[i] * 2;
    
    for (int i = 0; i < n; ++i)
        keys[i] = keys[i] ^ (pw[17] - 1);
    
    vector<bool> gist(pw[17], false);
    for (int key : keys)
        gist[key] = 1;
    
    for (int i = pw[17] - 1; i > 0; --i)
        if (gist[i])
            for (int j = 0; j < 17; ++j)
                if (i & pw[j])
                    gist[i - pw[j]] = true;
    
    int q; cin >> q;
    for (int i = 0; i < q; ++i)
    {
        int x; cin >> x;
        if (gist[x]) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution a bit?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 store which 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_bits will be [0,2,4,5,6,7,....15,16]. now using recursion we produce all the combinations of zero_bits i.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 in store.

      • Note that we will not repeat the recursion if it is already present in store.

      • 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_bits will be [0,2].

      • Finally we have to check if one_bits is present in store or not. If it is present, then answer is 'Yes', else 'No'.

      → Reply