No of pairs of elements whose XOR satisfies a condition We are given a set of $n$ non-negative integers. We need to find the number of pairs of integers from this set whose $XOR$ is $ = K$.
My approach is to sort the integers which takes $O(NlogN)$. Then for each element $a_i$ find $a_i\oplus K$. Make a binary search for the result. If it exists increment the counter. This can be done in a total of $O(NlogN)$.
Now, I want to extend the question to find number of such pairs whose $XOR$ is $\le K$. Obviously, an algorithm better than $O(N^2)$ is needed.
 A: Let's make the problem a little more general and have two sets of input numbers $A$ and $B$, and ask for the number of pairs $(a,b)\in A\times B$ such that $a \oplus b \le K$.
If $K=0$ then the answer is just $|A\cap B|$. Otherwise let $K=2^p+Q$ with $Q<2^p$. (This is just finding the most significant set bit in $K$).
Then partition both $A$ and $B$ into subsets according to the quotient $\lfloor a/2^p \rfloor$ for each number $a$. Whenever there's both a subset $A_i$ and a subset $B_i$ with the same quotient, that gives us $|A_i|\times|B_i|$ pairs that xor to something less than $K$ -- indeed, less than $2^p$.
On the other hand, we can also pair up the partitions such that the subset of $A$ corresponding to the quotient $x$ is matched up to the subset of $B$ corresponding to the quotient $x\oplus 1$. When we xor numbers from two such subsets together we get something between $2^p$ and $2^{p+1}$, which will be $\le K$ if the xor of the remainders is $\le Q$. Count the numbers of relevant pairs between the two partitions recursively.
If we start by setting $A=B=$ the input set, this algorithm gives the number of ordered pairs that xor to something $\le K$. We can get the number of unordered pairs instead by noting $(a,a)$ is a qualifying pair for every input number $a$ -- and these $n$ pairs are counted exactly once, whereas everything else was counted exactly twice. So to get the number of unordered pairs, add $n$ and divide by two at the very end. (Or subtract $n$ if you don't want to count $a\oplus a$ as "pairs" at all).

Time complexity. If we sort the set of input numbers once and for all at the beginning, the order will be preserved each time we take remainders for a recursive invocation of the algorithm, so the partitioning in each step takes linear time. Each of the $n$ input numbers ends up in at most one recursive call for each $p$, and there are at most $\log K$ levels in the recursion, so the total time complexity in $O(n\log n + n\log K)$.
It feels like it should be possible to prove that this running time is actually linear in the size of the the input in bits (rather than the number of input numbers), but the details of how to dispose of the $\log K$ factor are a bit murky if $K$ is larger than most but not all of the input numbers. Perhaps it isn't true.
