3

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.

Naveen Kumar Vunnam
  • 159
  • 1
  • 9
  • 1
    If it doesn't have something to do with [Why is processing a sorted array faster than processing an unsorted array?](https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array) I'll be surprised. – user4581301 Sep 18 '20 at 03:35
  • Wait a sec. Maybe not. If the array is sorted, elements with a low distance are close to one another. You don't have to fork around checking everything vs everything else. – user4581301 Sep 18 '20 at 03:37
  • I get it, elements that are close to one another always give the result that is less than the elements that are far away from each other – Naveen Kumar Vunnam Sep 18 '20 at 03:39

1 Answers1

4

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.

Laurent Jospin
  • 604
  • 5
  • 9