Найдите побитовое XOR всех триплетов, образованных из заданных трех массивов

Даны три массива arr1[] , arr2[] и arr3[], состоящие из неотрицательных целых чисел. Задача состоит в том, чтобы найти побитовое XOR XOR всех возможных троек, которые образуются путем взятия одного элемента из каждого массива.

Примеры:

Input: arr1[] = {2, 3, 1}, arr2[] = {2, 4}, arr3[] = {3, 5}
Output: 0
Explanation: All possible triplets are (2, 2, 3), (2, 2, 5), (2, 4, 3), (2, 4, 5), (3, 2, 3), (3, 2, 5), (3, 4, 3), (3, 4, 5), (1, 2, 3), (1, 2, 5), (1, 4, 3), (1, 4, 5). Bitwise XOR of all possible triplets are =(2^2^3) ^ (2^2^5) ^ (2^4^3) ^ (2^4^5) ^ (3^2^3) ^ (3^2^5) ^ (3^4^3) ^ (3^4^5) ^ (1^2^3) ^ (1^2^5) ^ (1^4^3) ^ (1^4^5) = 0

Input:  arr1[] = {1}, arr2[] = {3}, arr3[] = {4, 2, 3}
Output:7
Explanation: All possible triplets are (1, 3, 4), (1, 3, 2), (1, 3, 3)
Bitwise XOR of all possible triplets are =  (1^3^4) ^ (1^3^2) ^ (1^3^3) =7

Наивный подход :

The basic idea is to traverse the arrays and generate all possible triplets from the given arrays. Finally, print the Bitwise XOR of each of these triplets from the given arrays.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, totalXOR , для хранения побитового XOR каждой пары из этих наборов массивов.
• Пройдите заданные массивы и сгенерируйте все возможные триплеты (arr[i], arr[j], arr[k]) из заданных массивов.
• Для каждого триплета arr[i], arr[j] и arr[k] обновите значение:
  • totalXOR = (totalXOR ^ приб [i] ^ приб [j] ^ приб [k]).
• Наконец, верните значение totalXOR .

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

Выход:

0

Временная сложность: O(N * M * P), где N, M и P — размеры трех массивов.
Вспомогательное пространство: O(1)

Эффективный подход : чтобы оптимизировать описанный выше подход, следуйте приведенным ниже наблюдениям.

Property of Bitwise XOR: 
a ^ a  ^ . . .( Even times ) = 0
a ^ a ^ a ^ . . .( Odd times ) = a

Say the sizes of arr1[], arr2[] and arr3[] are N₁, N₂ and N₃ respectively. Element of arr1[] occurs exactly N₂ * N₃ times. Similarly, arr2[] occurs exactly N₃ * N₁ and element of arr3[] occur exactly N₁ * N₂ times.

Выполните следующие шаги, чтобы решить проблему:

• Для каждого массива проверьте, является ли количество вхождений его элементов нечетным или больше, используя приведенную выше формулу для вхождений:
  • Если количество вхождений нечетное, тогда XOR все элементы этого массива с окончательным результатом.
  • В противном случае перейти к следующему массиву.
• Возвращает окончательное значение XOR.

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

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