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

  algorithm, array-algorithms, c++, data-structures

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.

Source: Windows Questions C++

LEAVE A COMMENT