Сумма побитового И суммы пар и их побитового И из заданного массива

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти сумму побитового И (arr[i] + arr[j]) и побитового И между arr[i] и arr[j] для каждой пары элементы (arr[i], arr[j]) из заданного массива. Так как сумма может быть очень большой, выведите ее по модулю (109 + 7).

Примеры:

Input: arr[] = {8, 9}
Output: 0
Explanation: The only pair from the array is (8, 9). Sum of the pair = (8 + 9) = 17. Bitwise AND of the pairs = (8 & 9) = 8. Therefore required Bitwise AND = (17 & 8) = 0.

Input: arr[] = {1, 3, 3}
Output: 2
Explanation:
Pair (1, 3): Required Bitwise AND = (1 + 3) & (1 & 3) = (4 & 1) = 0.
Pair (3, 3): Required Bitwise AND = (3 + 3) & (3 & 3) = (6 & 3) = 2.
Therefore, total sum = 0 + 0 + 2 = 2.

Наивный подход: самый простой подход — сгенерировать все возможные пары из заданного массива и проверить, существует ли такая пара, которая удовлетворяет заданному условию или нет. Если окажется, что это правда, то посчитайте эту пару. После проверки всех пар выведите результат count .
Временная сложность: O(N ² )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать на основе следующих наблюдений:

• Учитывая пару (X, Y) , побитовое И в бите, скажем, b ^th равно 1 , тогда (X + Y) также должен иметь b ^-й бит в качестве установленного бита, чтобы внести вклад в b ^-й бит.
• Рассматривая только последние b битов обоих номеров таких пар, можно заметить, что для выполнения вышеуказанного условия должны быть установлены ^b бит и (b + 1 ⁾ бит.
• Следовательно, из приведенных выше шагов можно сделать вывод, что для выполнения вышеуказанных условий должно выполняться следующее условие:

• Таким образом, задача сводится к тому, чтобы найти количество пар, удовлетворяющих вышеуказанному условию для каждой битовой позиции, и увеличить результат на значение cnt*2 ^b для 0 ≤ b < 31 .

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, ans , чтобы сохранить результирующую сумму.
• Переберите диапазон [0, 30] и выполните следующие операции:
  • Инициализируйте вектор V , который хранит пары, удовлетворяющие вышеуказанным условиям.
  • Пройдите по заданному массиву arr[] и вставьте значение arr[j] – (arr[j] >> (i + 1))*(1 << (i + 1)) по модулю M в вектор V , если (( arr[j] >> (i + 1)) &1) верно.
  • Отсортируйте вектор V в порядке возрастания.
  • Пересеките вектор V и выполните следующее:
    • Вычислите значение 2 ^{(i + 1)} + 2 ⁱ – V[j] и сохраните его в переменной, скажем, Y .
    • Найдите количество точек в V , которое больше или равно Y в V , и сохраните его в переменной, скажем, cnt , т.е. cnt = V.size() – (lower_bound(V.begin() + j + 1, V.end (), Y) – V.begin()).
    • Обновите ответ как ans = (ans+ cnt* 2 ⁱ )%M .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

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