Количество пар в массиве, для которых побитовое И XOR пары и X равно 0

Дан массив arr[] , состоящий из N положительных целых чисел и положительного целого числа X , задача состоит в том, чтобы найти количество пар (i, j) , таких что i < j и (arr[i]^arr[j] )&X равно 0 .

Примеры:

Input: arr[] = {1, 3, 4, 2}, X = 2 
Output: 2
Explanation:
Following are the possible pairs from the given array:

1. (0, 2): The value of (arr[0]^arr[2])&X is (1^4)&2 = 0.
2. (1, 3): The value of (arr[1]^arr[3])&X is (3^2)&2 = 0.

Therefore, the total count of pairs is 2.

Input: arr[] = {3, 2, 5, 4, 6, 7}, X = 6
Output: 3

Наивный подход: простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные пары данного массива и подсчитать те пары (i, j) , которые удовлетворяют заданным критериям, т. е. i < j и (arr[i]^arr[j ] )&X is 0 .. После проверки всех пар выведите полученное общее количество .

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

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

Эффективный подход . Вышеупомянутый подход также можно оптимизировать, соблюдая данное уравнение. Итак, чтобы выполнить (A[i]^A[j]) & X == 0 , затем сбросьте биты в ответе (A[i]^A[j]) в той же позиции, где X установил биты в требуется его двоичное представление.

For Example, If X = 6  => 110, so to make (answer & X) == 0 where answer = A[i]^A[j], the answer should be 001 or 000. So to get the 0 bit in the answer (in the same position as the set bit the X has), it is required to have the same bit in A[i] and A[j] at that position as the Bitwise XOR of the same bit (1^1 = 0 and 0^0 = 0) gives 0.

Внимательно изучив отношение между X и A[i] и A[j] , можно обнаружить, что X&A[i] == X&A[j] . Следовательно, идея состоит в том, чтобы найти частоту элементов массива, имеющих значение arr[i]&X , и любые два числа с одинаковым значением можно составить как пару. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте неупорядоченную карту, скажем, M , чтобы хранить количество чисел, имеющих определенное значение arr[i]^X .
• Переберите диапазон [0, N], используя переменную i , и увеличьте количество значений arr[i]&X в неупорядоченной карте M .
• Инициализируйте переменную count как 0 , чтобы сохранить результирующее количество пар.
• Переберите карту M , используя переменную m , и добавьте значение (m.second)*(m.second – 1)/2 к переменной count .
• После выполнения вышеуказанных шагов выведите в качестве результата значение count .

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

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