Count pairs in array whose XOR is less than K

general
,
1

Given an array of N elements how to count all pairs whose XOR is less than equal to K??

2

One of the easiest solutions is iterating over the array and checking with each element if the XOR is less than K and maintaining a counter for the answer!

Pseudocode:

array of numbers of size N-> num[N]
for(i is less than N)
for(j is less than N)
if(num[i] XOR num[j] less than or equal to K)
counter++;
3

I need an approach having complexity less than O(n^2).

4

This is a well known problem (I think). You can use a trie as described here.

2 Likes