Количество подпоследовательностей, имеющих нечетные значения побитового И в данном массиве

Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы найти количество подпоследовательностей данного массива, таких что их значение побитового И является нечетным.

Примеры:

Input: arr[] = {2, 3, 1}
Output: 3
Explanation: The subsequences of the given array having odd Bitwise AND values are {3} = 3, {1} = 1, {3, 1} = 3 & 1 = 1.

Input: arr[] = {1, 3, 3}
Output: 7

Рекомендуется: сначала попробуйте свой подход на {IDE}, прежде чем переходить к решению.

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

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

Эффективный подход: вышеприведенный подход может быть оптимизирован с помощью наблюдение что для того, чтобы побитовое И значение набора целых чисел было нечетным, младший значащий бит каждого элемента набора должен быть установленным битом. Следовательно, чтобы подпоследовательность имела нечетное значение побитового И, все элементы подпоследовательности должны быть нечетными. Используя это наблюдение, данная проблема может быть решена с помощью следующих шагов:

• Создайте переменную odd , в которой хранится общее количество нечетных целых чисел в данном массиве arr[] . Инициализируйте его с 0 .
• Выполните итерацию по массиву и увеличьте значение нечетного на 1 , если текущее целое число является нечетным целым числом.
• Количество непустых подпоследовательностей массива, состоящего из X элементов, равно 2 ^X – 1 . Следовательно, количество непустых подпоследовательностей со всеми нечетными элементами равно 2 ^{нечетным} – 1 , что и является требуемым ответом.

Ниже приведена реализация подхода:

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