Побитовое XOR для одинаковых индексированных элементов массива после реорганизации массива, чтобы сделать XOR одинаковых индексированных элементов двух массивов равными

Имея два массива A[] и B[] , состоящие из N положительных целых чисел, задача состоит в том, чтобы выполнить побитовое XOR с одинаковыми индексированными элементами массива после перестановки массива B[] таким образом, чтобы побитовое XOR с одинаковыми индексированными элементами массивов A[ ] становится равным.

Примеры:

Input: A[] = {1, 2, 3}, B[] = {4, 6, 7}
Output: 5
Explanation:
Below are the possible arrangements:

• Rearrange the array B[] to {4, 7, 6}. Now, the Bitwise XOR of the same indexed elements are equal, i.e. 1 ^ 4 = 5, 2 ^ 7 = 5, 3 ^ 6 = 5.

After the rearrangements, required Bitwise XOR is 5.

Input: A[] = { 7, 8, 14 }, B[] = { 5, 12, 3 }
Output: 11 
Explanation:
Below are the possible arrangements:

• Rearrange the array B[] to {12, 3, 5}. Now, the Bitwise XOR of the same indexed elements are equal, i.e. 7 ^ 12 = 11, 8 ^ 3 = 11, 14 ^ 5 = 11.

After the rearrangements, required Bitwise XOR is 11.

Наивный подход: данная проблема может быть решена на основе наблюдения, что количество перестановок может быть не более N , потому что любой элемент в A[] может быть соединен только с N другими целыми числами в B[] . Итак, есть N возможных значений для X . Теперь просто XOR всех кандидатов с каждым элементом в A[] и проверьте, можно ли расположить B[] в таком порядке.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² *log(N))
Вспомогательное пространство: O(N)

Эффективный подход. Описанный выше подход также можно оптимизировать, не сортируя массив и сохраняя побитовое XOR всех элементов B[] , а затем побитовое XOR со всеми элементами C[] . Теперь, если результат равен 0 , это означает, что оба массива имеют одинаковые элементы. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, x , которая хранит XOR всех элементов массива B[].
• Инициализируйте набор, скажем, numbers[] , чтобы хранить только уникальные числа.
• Переберите диапазон [0, N), используя переменную i , и выполните следующие шаги:
  • Инициализируйте переменные- кандидаты как XOR для A[0] и B[i] и curr_xor как x , чтобы увидеть, равен ли он 0 после выполнения требуемых операций.
  • Переберите диапазон [0, N), используя переменную j , и выполните следующие шаги:
    • Инициализируйте переменную y как XOR A[j] и кандидата и XOR y с curr_xor.
  • Если curr_xor равен 0, то вставьте значение-кандидат в набор чисел[].
• После выполнения вышеуказанных шагов выведите набор чисел[] в качестве ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)