Проверьте, можно ли переупорядочить массив таким образом, чтобы arr[i] XOR arr[i+2] равнялось 0

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

Для заданного массива arr[] размера N задача состоит в том, чтобы проверить, можно ли переставить элементы массива таким образом, чтобы побитовое XOR для i -го и (i+2)-го элементов всегда равнялось 0 для любого значения i ( 0 ≤ я <N-2 )

Примеры:

Input: arr[] = {1, 1, 2, 2}, N = 4
Output: YES
Explanation: Rearrange the array like {1, 2, 1, 2}.
Here XOR of [1, 1] and XOR of [2, 2] is 0.  

Input: arr[] = {1, 2, 3, 4}, N = 4
Output: NO
Explanation: Here no such arrangement is possible such that arr[i] XOR arr[i+2] is 0.

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

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

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

Bitwise XOR of two elements is 0 only when both the elements are same.
Based on the above observation it can be understood that all the elements in the odd position must be same and all the elements in the even position must be same

Поэтому, когда есть только один уникальный элемент (потому что все элементы будут одинаковыми) или два уникальных элемента и их частоты совпадают с количеством нечетных и четных позиций массива, только тогда возможна такая перестановка.

Выполните шаги, указанные ниже, чтобы решить проблему.

  • Создайте одну unordered_map для подсчета количества уникальных элементов.
  • Пройдите массив и сохраните элементы массива в карте.
  • Считать количество различных типов элементов на карте.
  • Если count > 2 , то невозможно переупорядочить массив по альтернативной позиции.
  • Если count = 1 , то расположение возможно.
  • Если count = 2 , то возможны обе возможности:
    • Если размер массива ( N ) четный, частота обоих должна быть одинаковой.
    • Если размер массива нечетный, то частота одного элемента должна быть N/2 , а другого - N/2+1 .

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

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

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