### FameOfTheLegends's blog

By FameOfTheLegends, history, 2 months ago,

given an array with n elements, and Q queries consisting of an integer find whether there exists an element in the array such that it's bitwise and is zero

1<=n<10^5 , 1<=q<10^5.

Can anyone tell how to do this question.

• +8

 » 2 months ago, # |   0 Is there a constraint on how big the elements can be?
•  » » 2 months ago, # ^ |   +3 Since the query number is at most 10^5, any number greater than 10^5 can have its most significant bits removed till it's smaller than 10^5 without affecting the answer. So we can assume that the input array numbers too would be smaller than 10^5 (or can be made so)
 » 2 months ago, # |   0 Here you go!
 » 2 months ago, # | ← Rev. 3 →   -19 You can use Binary Tries.Create a Trie with the given array elements and then traverse the trie in accordance with the element given in the query (let x).If the ith bit of x is 1, see if the trie contains 0 for corresponding bit, and, if the ith bit of x is 0, just continue traversing trie.let m be the maximum element in the given array. Overall Time complexity : O((n+q)logm)Feel free to Correct me if I am wrong.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I think in worst case (x=0), you will have to go through the whole Trie which will be 2^(No of bits). That will be O(q*2^(No of bits)) for queries.
 » 2 months ago, # |   0 How you guys are making sure if his contest is over now?
•  » » 2 months ago, # ^ |   0 the contest is from 12 pm to 4 pm from 9 july. Also these previusly asked question from my friends.
 » 2 months ago, # | ← Rev. 3 →   +5 Alright, I'll try to describe the solution that I have in mind to the best of my ability. If you do not understand please feel free to ask any doubts. I assume that there are no duplicate numbers in the input, if there are then they can be safely ignored since they do not provide any valueLet the input numbers in the array be a1, a2, and so on...Let us consider a single query q.The task is to specify whether there exists any a1 such that a1^q = 0Let the one's complement of a1 be a1'.Then the two following 2 conditions are equivalenta1^q = 0 and a1'^q = qSo, if we were to store a1' in our array instead of a1, then the query would change to finding the existence of a number such that it has all the bits set at the given bits of q.Since the input numbers can only be as large as 10^5, we only need to concern ourselves with 17 bits.We can solve the modified problem by creating a bitset array that stores the answer for that number.To do this we initialize an array of size 1<<17 to all false. For all the numbers in the array, we find all its subsets and set them to true.This step takes almost 3^17 time (refer here for details — https://cp-algorithms.com/algebra/all-submasks.html)Now, for each query, just output the value at your constructed bitset array!
•  » » 2 months ago, # ^ |   0 "The task is to specify whether there exists any a1 such that a1^q = 0"I think it should be a1&q=0. (Bitwise AND not Bitwise XOR).
•  » » » 2 months ago, # ^ |   0 Sorry about the confusion. I wasn't using C++ operators, I was using the mathematical logic symbols (https://en.wikipedia.org/wiki/Logical_conjunction). You are right, they should be Bitwise AND
•  » » 2 months ago, # ^ |   0 Won't it be one's complement?
•  » » » 2 months ago, # ^ |   0 Yes, you are right, I updated the answer to reflect the change.Thankyou for pointing it out!
 » 2 months ago, # |   +6 There exists $O(MAX(a_i) \log MAX(a_i))$ using SOS dp.For a given mask, we want to compute the number of elements in the array that are a submask to it. Then, to answer a query $x$, we just check if $freq[\sim x]$ is non-zero. Run a SOS dp to do this and it takes above time complexity. AFAIK this is the same problem as the one you're asking: https://codeforces.com/contest/165/problem/E. You can look at the editorial there if you need more explanation.