HELP in Visa Coding Round Task

1

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)

2

My idea is to put all the numbers in the array in a trie and once your trie is loaded up precompute all the subtree sizes by a trivial dfs. After that, we will try to search k in our trie, whenever we encounter an unset bit let say the subtree size of the corresponding set bit is S hence for all such encounters we will add \frac{S(S-1)}{2} to our answer until we traverse through all the bits. Would be great if someone can confirm the idea, I might be wrong.

2 Likes
3

I had the exact same idea :raised_hands:

4

Nice, so this seems a correct solution then :+1:

1 Like
5

Thanks,I got the Idea.

1 Like