Подсчет подпоследовательностей с нечетными значениями побитового ИЛИ в массиве
Учитывая массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти количество подпоследовательностей из данного массива, значение побитового ИЛИ которых нечетно.
Примеры:
Input: arr = [2, 4, 1]
Output: 4
Explanation: Subsequences with odd Bitwise OR values are {1}, {2, 1}, {4, 1}, {2, 4, 1}Input: arr = [1, 3, 4]
Output: 6
Наивный подход. Самый простой подход к решению проблемы — сгенерировать все подпоследовательности заданного массива и для каждой подпоследовательности проверить, является ли ее значение побитового ИЛИ нечетным или нет. Если он нечетный, то увеличьте количество на единицу. После проверки всех подпоследовательностей выведите полученное количество.
Сложность времени:
Вспомогательное пространство:
Эффективный подход. Данную проблему можно решить, заметив, что для того, чтобы подпоследовательность имела нечетное значение побитового ИЛИ, хотя бы один элемент подпоследовательности должен быть нечетным. Следовательно, по крайней мере один элемент в подпоследовательности должен иметь младшую значащую цифру, равную 1. Для решения этой проблемы выполните следующие шаги:
- Сохраните количество четных и нечетных элементов, присутствующих в массиве arr[], в четных и нечетных переменных соответственно.
- Пройдите массив A[] с помощью переменной i
- Если значение A[i] нечетное, увеличьте значение нечетного на 1 .
- В противном случае увеличьте значение даже на 1 .
- Общее количество комбинаций хотя бы с одним нечетным элементом и любым количеством четных элементов может быть задано следующим образом: [2^(нечетные элементы) – 1] * 2^(четные элементы). Поскольку необходим хотя бы один нечетный элемент, пустой набор комбинаций из 1 исключается.
Ниже приведена реализация подхода:
Сложность времени:
Вспомогательное пространство: