Count pairs in array whose XOR is less than K

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

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!


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)

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

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