Максимизируйте побитовое XOR для K с двумя числами из массива

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

Для заданного целого числа K и массива arr[] размера N задача состоит в том, чтобы выбрать два элемента из массива таким образом, чтобы выполнялось побитовое исключающее ИЛИ. из тех двух с K (т.е. K ⊕ Первый выбранный элемент ⊕ Второй выбранный элемент ) является максимальным.

Примечание. Любой элемент массива можно выбрать любое количество раз.

Примеры:

Input: N = 3, K = 2, arr[]= [1, 2, 3]
Output: 3
Explanation: If we choose one element from the second index 
and another one from the third index, then the XOR of triplet 
will be 2 ^ 2 ^ 3 = 3, which is the maximum possible.

Input: N = 3, K = 7, arr[] = [4, 2, 3]
Output: 7
Explanation: If we choose both the element from the third index,  
then the XOR of triplet will be 7 ^ 3 ^ 3 = 7, which is the maximum possible.

Input: N = 3, K = 3, arr[] = [1, 2, 3]
Output: 3
Explanation: If we choose both the element from the third index,  
then the XOR of triplet will be 3 ^ 3 ^ 3 = 3, which is the maximum possible.

Наивный подход: подход к проблеме заключается в следующем:

Iterate over all the unique pairs in the array and find the xor value of the triplet and keep track of the maximum.

Выполните шаги, указанные ниже, чтобы реализовать вышеуказанную идею:

  • Используйте два вложенных цикла для создания всех уникальных пар.
  • Найдите xor каждой тройки arr[i] ⊕ arr[j] ⊕ K .
  • Найдите максимум xor для каждой пары.
  • В конце вернуть максимальное полученное значение xor.

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

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

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

  • To maximize the xor of the triplet iterate over all the elements considering them as the second element. and choose the third element efficiently in such a way that the xor of triplet is maximum possible.
  • Maximize the XOR by choosing the other elements in such a way that the resultant bit is 1 most of the time, and give priority to the MSB first then to the LSB because the contribution of MSB is always greater than the LSB in final decimal value. 
  • For this, traverse from the MSB to LSB and if the bit is set then we will search for 0 so that the resultant bit is 1 and vice versa.
  • Use Trie data structure. Because in order to maximize the xor value, we need to do the prefix search for the complement of that number, which can be done efficiently using trie. 

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

  • Сначала добавьте все элементы в trie .
  • Каждый бит в числе имеет 2 возможности: 0 и 1. Итак, у нас есть 2 указателя в каждом узле Trie:
    • child[0] -> указывает на 0 бит &
    • child[1] -> указывает на 1 бит.
  • Теперь вставьте все элементы в дерево.
    • Используйте набор битов размером 32 ( bitset<32> B ) и перейдите от старшего бита (MSB) к младшему биту (LSB).
    • Теперь начните с корня Trie и проверьте, присутствует ли дочерний элемент [0] или дочерний элемент [1] (не NULL), в зависимости от текущего бита B[j] ( j находится в диапазоне от 0 до бита общего числа) числа .
    • Если он присутствует, перейдите к его дочернему элементу, если нет, создайте новый узел в этом дочернем элементе ( 0 бит или 1 бит) и перейдите к его дочернему элементу.
  • Теперь пройдитесь по массиву и считайте каждый элемент вторым выбранным элементом .
  • До сих пор текущее значение XOR триплета равно K ^ arr[i] .
  • Теперь найдите третий элемент с помощью trie, чтобы его xor с текущим xor был максимальным.
    • Начните с корня Trie и со старшего бита числа (инициализируйте ans = 0 , чтобы сохранить ответ).
    • Если текущий бит установлен в текущем xor, перейдите к дочернему [0] , чтобы проверить, не является ли он NULL.
      • Если это не NULL, добавьте 2 i-1 к ответу (потому что этот бит будет установлен в ответе), иначе перейдите к child[1] .
    • Если он не установлен, перейдите к child[1] , чтобы убедиться, что он не NULL.
      • Если это не NULL, мы добавляем 2 i-1 к ans, иначе мы идем к child[0] .
  • Найдите максимум (скажем, maxi ) среди максимально возможных xor для каждого индекса.
  • Верните макси в качестве ответа.

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

Временная сложность: O(N * logM), где M — максимальный элемент массива.
Вспомогательное пространство: O(logM)

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