Найдите сумму XOR побитового И всех пар из заданных двух массивов

Опубликовано: 22 Сентября, 2022

Учитывая два массива A и B размеров N и M соответственно, задача состоит в том, чтобы вычислить сумму XOR побитовых И всех пар A и B

Примеры:

Input: A={3, 5}, B={2, 3}, N=2, M=2
Output:
0
Explanation:
The answer is (3&2)^(3&3)^(5&2)^(5&3)=1^3^0^2=0.

Input: A={1, 2, 3}, B={5, 6}, N=3, M=2
Output:
0

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

  1. Инициализируйте переменную ans значением -1 , в которой будет храниться окончательный ответ.
  2. Перейдите массив A и сделайте следующее:
    1. Для каждого текущего элемента пройдитесь по массиву B и сделайте следующее:
      1. Если ans равно -1 , сохраните побитовое И элементов в ans.
      2. В противном случае сохраните побитовое XOR для ans и побитовое AND для элементов в ans .
  3. Возврат ответ.

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

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

Эффективный подход:

Наблюдение: распределительное свойство XOR над AND может быть использовано для решения проблемы.

let A[] = [a, b, c] 
let B[] = [d, e] 
Result : 
(a & d) ^ (a & e) ^ (b & d) ^ (b & e) ^ (c & d) ^ (c & e) 
By applying distributive property, 
[(a ^ b ^ c) & d] ^ [(a ^ b ^ e) & e] 
(a ^ b ^ c) & (d ^ e) 
 

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

  • Инициализируйте две переменные ans1 и ans2 равными 0 , в которых будут храниться побитовые суммы XOR первого массива и второго массива соответственно.
  • Траверс A и для каждого текущего элемента:
    • Сохраните побитовое XOR для ans1 и текущий элемент в ans1 .
  • Траверс B и для каждого текущего элемента:
    • Сохраните побитовое XOR для ans2 и текущий элемент в ans2 .
  • Вернуть ответ1&ответ2.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ