4
\$\begingroup\$

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!

\$\endgroup\$
2

2 Answers 2

2
\$\begingroup\$

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;
    }
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.