Can someone help me in the following problem
Given an array consisting of n integers and q queries. And in each query there is an integer x for which you need to report that is there any number in the array such that its bitwise and with x is zero.
1<=N,Q<=10^5,1<=arr[i]<=10^9
I tried doing this problem using Trie but couldn’t get the most optimised solution. Can someone help.
I am pretty much interested to solve Trie based problems. Gave a thought about solving this problem using Trie (irrespective of whether it can be solved using it or not).
#include <bits/stdc++.h>
#define BINARY_LENGTH 32
using namespace std;
class Trie {
public:
class Node {
public:
map<char, Node*> next;
};
Node* root;
Trie() {
root = new Node();
}
void insert(string& s) {
Node* node = root;
for(char& ch: s) {
if(node -> next[ch] == nullptr) {
node -> next[ch] = new Node();
}
node = node -> next[ch];
}
}
bool dfs(string& s, int index, Node* node) {
if(index == (s.length())) {
return true;
}
// If s[index] is '1', the other bit must be '0'
if(s[index] == '1') {
if(node -> next['0'] == nullptr) {
return false;
}
return dfs(s, index + 1, node -> next['0']);
}
else {
if(node -> next['0'] != nullptr) {
if(dfs(s, index + 1, node -> next['0'])) {
return true;
}
}
if(node -> next['1'] != nullptr) {
if(dfs(s, index + 1, node -> next['1'])) {
return true;
}
}
return false;
}
}
bool find(string& s) {
Node* node = root;
return dfs(s, 0, node);
}
};
string bin(int n) {
string binary;
for(; n; binary.push_back((n & 1) + '0'), n >>= 1);
binary.resize(BINARY_LENGTH, '0');
reverse(binary.begin(), binary.end());
return binary;
}
int main() {
int n = 0;
cin >> n;
Trie trie;
for(int i = 0; i < n; i++) {
int a = 0;
cin >> a;
string binary = bin(a);
trie.insert(binary);
}
int q = 0;
cin >> q;
for(int i = 0; i < q; i++) {
int a = 0;
cin >> a;
string binary = bin(a);
cout << (trie.find(binary) ? "YES" : "NO") << '\n';
}
return 0;
}
My Approach should be pretty clear from the code. It performs depth-first-search for each query. Ignore it If your approach is also the same.
PS: I am not sure about the time complexity of my code.
Edit: It seems my approach is bad. It took around 15s for worst input, which is obviously inefficient 