Уменьшите двоичный массив, заменив обе пары 0 или обе пары 1 на 0 и 10 или пару 01 на 1.

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

Учитывая двоичный массив arr[] размера N , задача состоит в том, чтобы найти последнее число, оставшееся в массиве после выполнения набора операций. В каждой операции выберите любые два числа и выполните следующее:

  • Если оба числа совпадают, удалите их из массива и вставьте 0 .
  • Если оба числа разные, удалите их оба и вставьте 1 .

Пример:

Input: arr[]={0, 0, 1}
Output: 1
Explanation: There are two possible sequence of operations as follows:

  • arr[] = {0, 0, 1}, delete (0, 1) and insert 0 => arr[] = {0, 0}, delete (0, 0) and insert 1=> arr[] = {1}.
  • arr[] = {0, 0, 1}, delete (0, 0) and insert 0 => arr[] = {0, 1}, delete (0, 1) and insert 1=> arr[] = {1}.

Hence the remaining element is 1.

Input: arr[]={1, 0, 0, 0, 1}
Output: 0

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  • 2 одинаковых числа заменяются на 0.
  • 2 разных числа заменяются на 1.

Теперь создадим таблицу для каждого результата:

При внимательном рассмотрении приведенной выше таблицы можно заметить, что таблица представляет собой побитовую операцию XOR. Следовательно, оставшееся целое число будет равно побитовому XOR для заданных элементов массива, что может быть дополнительно упрощено, как если бы частота 1 была четной, результат был бы 0 , иначе это 1 .

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

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

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