Подсчет подпоследовательностей с нечетными значениями побитового исключающего ИЛИ из массива

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

Учитывая массив A[] размера N , задача состоит в том, чтобы подсчитать количество подпоследовательностей из данного массива, чье значение побитового исключающего ИЛИ нечетно.

Примеры:

Input: A[] = {1, 3, 4}
Output: 4
Explanation: Subsequences with odd Bitwise XOR are {1}, {3}, {1, 4}, {3, 4}.

Input: A[] = {2, 8, 6}
Output: 0
Explanation: No such subsequences are present in the array.

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

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

Эффективный подход. Чтобы оптимизировать описанный выше подход, идея основана на наблюдении, что подпоследовательность будет иметь нечетное побитовое исключающее ИЛИ только в том случае, если количество нечетных элементов, присутствующих в ней, является нечетным. Это связано с тем, что нечетные элементы имеют младший значащий бит, равный 1 . Следовательно, XOR младших значащих битов ( 1 ^ 1 ^ 1…. ) до нечетного числа раз устанавливает младший значащий бит нового сформированного числа. Следовательно, новое образовавшееся число является нечетным.
Выполните следующие шаги, чтобы решить проблему:

  1. Сохраните количество четных и нечетных элементов, присутствующих в массиве A[], в четных и нечетных значениях соответственно.
  2. Обход массива A[] с использованием переменной i
    • Если значение A[i] нечетное, увеличьте значение нечетного на 1.
    • В противном случае увеличьте значение даже на 1 .
  3. Если значение нечета равно 0 , то выведите 0 и вернитесь.
  4. В противном случае,
    • Найдите все комбинации с нечетным числом нечетных элементов.
    • Это можно рассчитать по формуле ( X C 1 + X C 3 +…+ X C (x-(x+1)%2) ) * ( M C 0 + M C 1 +…+ M C M ) = 2 X- 1 * 2 М = 2 Х+М-1 = 2 Н-1 .
    • Следовательно, выведите 2 N-1

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

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