Подсчитайте упорядоченные пары элементов массива, такие что побитовое И для K и XOR пары равно 0

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

Учитывая массив arr[] размера N и целое число K , задача состоит в том, чтобы найти количество всех упорядоченных пар ( i, j ), где i != j , таких, что ((arr[i] ⊕ arr[j] ) & К) = 0 . ⊕ представляет собой побитовое XOR, а & представляет побитовое AND.

Примеры :

Input: arr = [1, 2, 3, 4, 5], K = 3
Output: 2
Explanation: There are 2 pairs satisfying the condition. 
These pairs are: (1, 5) and (5, 1)

Input: arr = [5, 9, 24], K = 7
Output: 0
Explanation: No such pair satisfying the condition exists.

Подход : Данная проблема может быть решена с помощью следующей идеи:

Using distributive property, we can write ((arr[i] ⊕ arr[j]) & K) = ((arr[i] & K) ⊕ (arr[j] & K)). 
Since for ((arr[i] & K) ⊕ (arr[j] & K)) = 0, these two terms (arr[i] & K) and (arr[j] & K) must be equal.

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

  • Создайте карту и переменную ответа (скажем, Res = 0 ).
  • Перейдите массив и вставьте ( arr[i] & K ), чтобы отобразить его количество.
  • Теперь пройдитесь по карте и для каждой записи, если есть X таких вхождений, тогда возможные пары = X*(X-1) . Так что добавьте это к значению Res .
  • Верните Res в качестве требуемого ответа.

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

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

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