triggered_'s blog

Help In Interview Problem
By triggered_, history, 4 years ago, In English

Q.Find the number of pairs in the array whose bitwise AND is greater then K?

Size of Array: N=5*(10^5)

Elements in Array: (10^9)>=a[i]>=1

Range for K: (10^9)>=K>=0

Expected Time Complexity: O(N) or O(NlogN)

  • Vote: I like it
  • -16
  • Vote: I do not like it

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

It's better to add your approach to the blog than just posting a question. A possible approach could be using some tree structure to store the numbers you have seen so far and somehow traverse the tree to find the count of numbers whose AND with the current element will be > K.

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

You can solve this using SOS dp. Iterate over i, now we want to find j such that a[i] & a[j] >= K. It's easy to see that there are log masks such that a[i] & a[j] >= K is equivalent to a[j] includes one if the masks(a[j] & mask == mask). This can be solved using sum over subset dp

→ Reply