Подсчитайте все триплеты из заданного массива, чье побитовое XOR равно K

Дан массив arr[] , который содержит N положительных целых чисел и целое число K . Задача состоит в том, чтобы посчитать все триплеты, XOR которых равен K . т.е. arr[i] ^ arr[j] ^ arr[k] = X , где 0 ≤ i <j <k <N (индексирование на основе 0)

Примеры:

Input: arr[] = { 2, 1, 3, 7, 5, 4}, K = 5
Output: 2
Explanation: In the above array there are two triplets whose xor is equal to K
{ 2, 3, 4}, ( 2 ^ 3 ^ 4 = 5) 
{1, 3, 7}, ( 1 ^ 3 ^ 7 = 5 )
So, output is 2. 

Input: arr[] = { 4, 1, 5, 7}, X=0
Output:1
Explanation: In the above array there is only one triplet whose xor is equal to K
{ 4, 1, 5} (4 ^ 1 ^ 5=0)

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

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

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

Эффективный подход . Проблема может быть эффективно решена с помощью сортировки, бинарного поиска и свойств xor, основанных на следующей идее:

Sort the array and then run two nested loops to select two elements of the possible triplet. Use binary search to find if the third element is present or not with the help of Xor property (if a ^ x = K then a ^ K = x). If found, then there is possible triplet.

Для реализации идеи выполните следующие шаги:

• Отсортируйте заданный массив в порядке неубывания.
• Создайте цикл for, который будет указывать на первое число троек.
  • Сделать вложенный цикл for, который будет указывать на второе число триплета
    • Третье число будет таким: Third_ele = X ^ arr[ i ] ^ arr[ j ] , потому что если a^b^c = d, то c = d^a^b (свойство xor).
    • Выполните бинарный поиск в [j+1, N-1]. Если в этом диапазоне присутствует Third_ele , увеличьте количество на 1.
• Наконец верните счет .

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

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