Сумма побитового И всех неупорядоченных троек массива

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

Для данного массива 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)

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