Сумма побитового И всех неупорядоченных троек массива
Для данного массива arr[] , состоящего из N положительных целых чисел, задача состоит в том, чтобы найти сумму побитового И всех возможных троек (arr[i], arr[j], arr[k]) , таких что i < j < k .
Примеры:
Input: arr[] = {3, 5, 4, 7}
Output: 5
Explanation: Sum of Bitwise AND of all possible triplets = (3 & 5 & 4) + (3 & 5 & 7) + (3 & 4 & 7) + (5 & 4 & 7) = 0 + 1 + 0 + 4 = 5.Input: arr[] = {4, 4, 4}
Output: 4
Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные триплеты (i, j, k) данного массива так, что i < j < k , и вывести сумму побитового И всех возможных триплетов.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N 3 )
Вспомогательное пространство: O(1)
Эффективный подход. Описанный выше подход также можно оптимизировать, принимая во внимание двоичное представление чисел. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте переменную, скажем , как 0 , которая хранит результирующую сумму побитового И всех возможных триплетов.
- Повторите цикл в диапазоне [0, 31] и выполните следующие шаги:
- Инициализируйте переменную, скажем, cnt как 0 , которая хранит количество элементов массива, имеющих установленный i -й бит .
- Пройдите по заданному массиву и, если i-й бит установлен, увеличьте значение cnt на 1 .
- После вышеуказанного шага для всех возможных троек, имеющих i-й бит, он вносит значение (( cnt C 3 )*2 i ) в результирующую сумму. Поэтому добавьте это значение в переменную cnt .
- После выполнения вышеуказанных шагов выведите в качестве результата значение ans .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(1)