Максимизируйте сумму младших разрядов побитового ИЛИ всех возможных пар N/2 из данного массива

Дан массив arr[] , состоящий из N положительных целых чисел, где N четно, задача состоит в том, чтобы сформировать N/2 пар так, чтобы сумма наименьшего значащего бита побитового ИЛИ всех этих пар была максимальной.

Примеры:

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 8
Explanation:
On forming the pairs as (8, 4),(6, 2),(1, 3),(5, 7), the Bitwise OR of the pair is given by:
8 OR 4 = 12 and LSB = 4
6 OR 2 = 6 and LSB = 2
1 OR 3 = 3 and LSB = 1
5 OR 7 = 7 and LSB = 1
The sum of all the LSB is 4 + 2 + 1 + 1 = 8, which is maximum possible sum.

Input: arr[] = {1, 2, 3, 4, 5}
Output: 3

Подход: Данную проблему можно решить, найдя младший бит каждого элемента массива arr[i] и сохранив их в другом массиве, скажем, lsb_arr[] и отсортировав этот массив в порядке убывания. Теперь достаточно хранить только LSB каждого элемента массива, потому что в ответе требуется учитывать только LSB. Таким образом, для операции побитового ИЛИ можно использовать только младшие биты. Теперь рассмотрим каждую пару (i, i + 1) и прибавим к результату минимум из этих двух. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте список lsb_arr[] для хранения младшего значащего бита всех элементов массива arr[i] .
• Пройдите через диапазон [0, N) и сохраните младший бит каждого arr[i] в lsb_arr[] .
• Отсортируйте список lsb_arr[] в порядке убывания.
• Инициализируйте переменную an как 0 , чтобы сохранить результирующую сумму наименее значащих битов.
• Пройдите через диапазон [0, N) с помощью переменной i и добавьте значение элемента в позиции (i + 1) к переменной ans и увеличьте значение i на 2 .
• После выполнения вышеуказанных шагов выведите значение ans в качестве результата.

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

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