How does sorting an array help in finding min(Arr[i] xor Arr[j]) (where i not equal to j)?

user_13163286 0
Viewed 259

I recently stumbled upon a problem on HackerEarth. The problem statement asks us to find the min(Arr[i] xor Arr[j]) for the given array

In the editorial section, the problem author did something like this

    sort(a,a+n);
    long long ans = INT_MAX;
    for(int i=0;i<n-1;i++)
    {
        ans = min(ans, a[i]^a[i+1]);
    }

The author mentioned that the above code always produces the optimal result and didn't explain why. I'm quite curious to know the proof.

array-algorithms data-structures algorithm c++
1 Answers

Ok, so the point is, if you have a list of finite numbers Arr encoded in binary, you have a maximum most significant bit and all the other bits will always be 0, thus stays 0 when xored.

Now the min of min(Arr[i] xor Arr[j]) is obtained when Arr[i] and Arr[j] are the pair of numbers with the longest chain of similar most significant bits. If the array is sorted, those two are right next to one another, if they were not it would be possible to find a pair with even more successive most significants bits by taking a value in between and one of the sides.

Note that the sign bit might pose some problems here, I think this method works only for unsigned numbers.

user_57211250
Related