Minimum XOR value : Given an integer array A of N integers, find the pair of integers in the array which have minimum XOR value

Question

Given an integer array A of N integers, find the pair of integers in the array which have minimum XOR value Here is the Brute Force solution where we find every pair possible and compute XOR and find the minimum of every pair :

int minXOR(int arr[], int n) 
{ 
    int min_xor = INT_MAX; // Initialize result 

    // Generate all pair of given array 
    for (int i = 0; i < n; i++) 
        for (int j = i + 1; j < n; j++) 

            // update minimum xor value if required 
            min_xor = min(min_xor, arr[i] ^ arr[j]); 

    return min_xor; 
} 

Here is the code with O(n*logn) complexity :

int Solution::findMinXor(vector<int> &A) {
    sort(A.begin(),A.end());
    int min=INT_MAX;
    int val;
    for(int i=0;i<A.size();i++)
    {
        val=A[i]^A[i+1];
        if(val<min)
            min=val;
    }
    return min;
}

My doubt is, how does sorting help in finding the minimum xor valued pairs ? In this solution we are finding the xor of only the consecutive sorted elements. Will we not be missing out other potential minimum xor value pairs that are not consecutive ? I'm still learning bit manipulations, so forgive me if this doubt seems too stupid.

Answer 1

XOR is monotonic in the absolute difference between numbers. (If the numbers are identical, then the XOR is zero). If you ignore the possibility of negative numbers and write the numbers in binary, it becomes obvious.

So the minimum value in a sorted list will always be between a particular adjacent pair. And finding that pair is an O(N) traversal.

Answer 2

I must admit that I don't understand the most upvoted answer by @Bathseba: xor is not monotonic in the absolute difference between its arguments, see the comment by @OfekShilon.

The property can be proven e.g. by complete induction. Here is the main idea:

Consider a few different numbers in binary representation, in ascending order:

N = 6
A[1] = 10001
A[2] = 10011
A[3] = 11000
A[4] = 11100
A[5] = 11110
A[6] = 11111

Let x = A[1] xor A[N]. Let k be the position of the leftmost 1 in x's bit representation, counting from the right. Here: x = 10001 xor 11111 = 01110, and k = 5 (using the convention k = 1 for the least significant bit). All bits left to k (that is, on more significant positions) are the same in each number, hence they could be neglected or even set to zero. In our example, all bits at position 5 (ones), 6 (zeroes), 7(zeroes), etc, are irrelevant. We can consider only bits 1,...,k.

The case N=2 is trivial, so assume we have at least 3 numbers.
We can divide the numbers into two disjoint subsets (or, actually, subesequences), B_0 = {numbers with the k-th bit set to 0}, B_1 = {numbers with the k-th bit set to 1}.

B_0:
A[1] = 10001
A[2] = 10011

B_1:
A[3] = 11000
A[4] = 11100
A[5] = 11110
A[6] = 11111

None of them is empty. Each has less than N elements. One of them has at least 2 elements (recall that N > 2). In the pair that minimizes A[i] xor A[j], both numbers must belong to the same subset, either B_0 or B_1, for only such combination produces a number with the k-th bit (and all more significant bits) set to 0. This suffices to prove the statement that the pair that minimizes the xor must be one of the pairs of consecutive elements of A (we can reduce the N-element problem to a problem with a smaller number of elements, and the "theorem" is trivially true for N=2, so the complete induction will do the job).