Минимизируйте вставки в массив, чтобы разделить его попарно с помощью побитового XOR как X

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

Учитывая массив arr длины N различных чисел и целое число X , задача состоит в том, чтобы найти минимальное количество элементов, которые следует добавить в массив, чтобы элементы массива можно было сгруппировать в пары, где побитовое исключающее ИЛИ каждой пары равно Х.

Примеры:

 Input: N = 3, arr[] = {1, 2, 3}, X = 1
Output: 1
Explanation: If we add 0 to the array then the array becomes  {1, 2, 3, 0}. 
This array can be split as (1, 0), (2, 3), where XOR of each pair is 1.

Input: N = 5, arr[] = {1, 4, 5, 6, 7}, X = 7
Output: 3
Explanation: If we add (2, 0, 3) to the array, it becomes [1, 4, 5, 6, 7, 2, 0, 3]. 
This array can be split as (1, 6), (4, 3), (5, 2), (7, 0), with XOR of each pair as 7.

Подход: проблема может быть решена с использованием свойств побитового оператора XOR :

According to question, let us assume that each pair of Array has bitwise XOR value as X, i.e.

arr[i] ⊕ arr[j] = X

Since above statement is true, therefore below statement will also be true

arr[i] ⊕ X = arr[j]

Основываясь на приведенном выше соотношении, мы можем решить эту проблему следующим образом:

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

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

  • Создайте массив частот, чтобы сохранить частоту элементов массива.
  • Вставьте первый элемент массива в структуру хеш-данных.
  • Запустите цикл от i = 1 до N-1 :
    • Проверить, есть ли A[i] ⊕ X в массиве или нет.
    • Если не найден, вставьте текущий элемент в структуру хеш-данных.
    • В противном случае уменьшите частоту этого элемента.
  • Возвращает общее количество элементов, которые еще не сформировали пару.

Ниже приведена реализация описанного выше подхода.

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

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