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

Опубликовано: 25 Февраля, 2023

Для заданного двоичного массива A[] и целого числа X задача состоит в том, чтобы проверить, можно ли разделить A[] ровно на X непустых и непересекающихся подмассивов, так что каждый A i принадлежит ровно одному подмассиву, а побитовое XOR каждого подмассива одинаков.

Примеры:

Input: A[] = {0, 1, 1, 0, 0},  X = 3 
Output: Yes

Explanation: One of the possible ways of dividing A is {0}, {1, 1} & {0, 0}. Here XOR of each subarray is 0.

Input: A[] = {1, 1, 1}, X = 2 

Output: No

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

The bitwise XOR of any binary array is either 0 or 1. Therefore if an answer exists then it is either X non-overlapping subarrays having XOR equal to 1 or X non – overlapping subarrays having XOR equal to 0. We can iterate over the binary array and check whether we can divide the array into X non-overlapping subarrays having XOR equal to 0 or X non-overlapping substrings having XOR equal to 1.

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

  • Сначала установите xor = 0, count0 = 0 и count1 = 0.
  • Повторите цикл, чтобы подсчитать, сколько раз xor префиксного элемента массива равен 0. Предположим, что счетчик равен count0.
  • После этого проверьте count0 ≥ X и xor != 1 , если верно, то верните «Да».
    • Если это не так, установите xor = 0.
    • Повторите еще один цикл, чтобы подсчитать, сколько раз xor элемента префикса массива равен 1, и сбросьте xor = 0. Предположим, что счетчик равен count1.
    • После этого проверяем count1 ≥ X и (count1 – X) % 2 == 0 , если верно, то возвращаем «Да».
    • В противном случае верните «Нет».

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

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

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