# Find minimum XOR values in a given array

I am implementing an algorithm to find the pair of integers in the given array which have minimum XOR value.

Ex:

Input:

   0 2 5 7


Output:

   2 (value of 0 XOR 2).


Then bellow is my solution:

    public int findMinXor(List<int> A)
{
var min = int.MaxValue;

for (int i = 0; i < A.Count - 1; i++)
{
for (int j = i + 1; j < A.Count; j++)
{
var tmp = A[i] ^ A[j];

if (tmp < min)
{
min = tmp;
}

}
}

return min;
}


What should I do to improve the solution (clean code, performance, DRY,...)? Any help are appriciate!

• Spoiler at geeksforgeeks.org/minimum-xor-value-pair :) Oct 9, 2018 at 19:58
• Thanks Martin. Your information is really helpful. Oct 11, 2018 at 6:58

## Algorithms:

1. You can sort the array, and compare continuously pairs instead of compare every pairs. Then the result is minimum of continuously pairs.
2. Compare Array with count < 1 is no meaning
3. If there are only 2 numbers, then don't need the loop.

Take my solution as bellow:

        public int findMinXor(List<int> A)
{
if (A.Count <= 1)
{
throw new InvalidEnumArgumentException("list must be contain more than 2 numbers.");
}

if (A.Count == 2)
{
return A[0] ^ A[1];
}

var min = int.MaxValue;
A.Sort();

for (int i = 1; i < A.Count; i++)
{
var tmp = A[i] ^ A[i - 1];

if (tmp < min)
{
min = tmp;
}

}

return min;
}


The program is running in quadratic time. As usual, to improve performance you need to change the algorithm.

Sort the numbers into 32 buckets, according to where the most significant bit of the number is. Convince yourself that if a bucket contains more than one number, it makes no sense to test them against the numbers from other buckets (the result is guaranteed to not be minimal). A cross-bucket xor should be tested only if two adjacent buckets contain just one number each.

Work recursively with each bucket.