Минимальное значение XOR: если задан целочисленный массив A из N целых чисел, найдите в массиве пару целых чисел с минимальным значением XOR.

Question

Учитывая целочисленный массив A из N целых чисел, найдите в массиве пару целых чисел, которые имеют минимальное значение XOR. Вот решение грубой силы, где мы находим каждую возможную пару, вычисляем XOR и находим минимум каждой пары:

int minXOR(int arr[], int n) 
{ 
    int min_xor = INT_MAX; // Initialize result 

    // Generate all pair of given array 
    for (int i = 0; i < n; i++) 
        for (int j = i + 1; j < n; j++) 

            // update minimum xor value if required 
            min_xor = min(min_xor, arr[i] ^ arr[j]); 

    return min_xor; 
} 

Вот код со сложностью O (n * logn):

int Solution::findMinXor(vector<int> &A) {
    sort(A.begin(),A.end());
    int min=INT_MAX;
    int val;
    for(int i=0;i<A.size();i++)
    {
        val=A[i]^A[i+1];
        if(val<min)
            min=val;
    }
    return min;
}

Я сомневаюсь, как сортировка помогает найти минимальные пары xor? В этом решении мы находим xor только последовательно отсортированных элементов. Не будем ли мы упустить другие потенциальные пары минимальных значений xor, которые не являются последовательными? Я все еще учусь немного манипулировать, так что прости меня, если это сомнение кажется слишком глупым.

Answer 1

XOR является монотонным c в абсолютной разнице между числами. (Если числа идентичны, то XOR равен нулю). Если вы игнорируете возможность отрицательных чисел и записываете числа в двоичном виде, это становится очевидным.

Таким образом, минимальное значение в отсортированном списке всегда будет между конкретной соседней парой. И обнаружение этой пары является O (N) обходом.