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.

Pannier

geeksforgeeks.org/minimum-xor-value-pair – Hydroplane

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.

Yesseniayester

How is xor monotonic? Xor(8, 7) =15 is larger than xor(8, any number<7) – Hepta

So does that mean xor of 2 smaller numbers will always be less than a larger number ? – Pannier

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).

Hendel

Answer 3

XOR of smaller numbers is small so basically think of it as this for 2 numbers 2 and 3 whose binary representation goes as 010 for 2 and 011 for 3 if you perform xor for these two the answer would be 001 which is 1. The same way if you do xor for 2(010) and 4(100) the answer would be 110 which is 6. So basically as the number increases their xor value also increases. Hence, sorting the array gives us the min xor value pair in the least no of iterations.

Vish

Answer 4

Java code with O(n*logn) complexity

    public int findMinXor(ArrayList<Integer> A) {
    Collections.sort(A);
    int res = Integer.MAX_VALUE;
    for(int i = 0; i < A.size()-1; i++){
    
        int temp = A.get(i)^A.get(i+1);
        if(res > temp){
                res = temp;    
        }
       
    }
    return res;

Whelk

Please add some explanation not just paste the code. – Grotesquery