Сумма побитового XOR элементов массива со всеми элементами другого массива

Учитывая массив arr[] размера N и массив Q[] , задача состоит в том, чтобы вычислить сумму побитового исключающего ИЛИ всех элементов массива arr[] с каждым элементом массива q[].

Примеры:

Input: arr[ ] = {5, 2, 3}, Q[ ] = {3, 8, 7}
Output: 7 34 11
Explanation:
For Q[0] ( = 3): Sum =  5 ^ 3 + 2 ^ 3 + 3 ^ 3 = 7.
For Q[1] ( = 8): Sum = 5 ^ 8 + 2 ^ 8 + 3 ^ 8 = 34.
For Q[2] ( = 7): Sum = 5 ^ 7 + 2 ^ 7 + 3 ^ 7 = 11.

Input: arr[ ] = {2, 3, 4}, Q[ ] = {1, 2}
Output: 10 7

Наивный подход: самый простой подход к решению проблемы — пройтись по массиву Q[] и для каждого элемента массива вычислить сумму его побитового исключающего ИЛИ со всеми элементами массива arr[] .

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

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

• Инициализировать массив count[] размером 32 . для хранения количества установленных битов в каждой позиции элементов массива arr[].
• Пройдите массив arr[] .
• Обновите массив count[] соответствующим образом. В 32-битном двоичном представлении, если i ^-й бит установлен, увеличьте количество установленных битов в этой позиции.
• Пройдитесь по массиву Q[] и для каждого элемента массива выполните следующие операции:
  • Инициализируйте переменные, скажем, sum = 0, чтобы сохранить требуемую сумму побитового исключающего ИЛИ.
  • Итерация по каждой битовой позиции текущего элемента.
  • Если текущий бит установлен, добавьте количество элементов с i ^-м битом, не установленным * 2 ⁱ суммировать .
  • В противном случае добавьте count[i] * 2 ⁱ .
  • Наконец, выведите значение sum .

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

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