Найдите такое расположение массива, чтобы префикс ИЛИ был максимальным для каждого индекса.

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

Примеры:

Input: N = 4, arr[] = [1, 2, 4, 8] 
Output: [8, 4, 2, 1]
Explanation:  Prefix of the rearranged array is [8, 8 | 4, 8 | 4 | 2, 8 | 4 | 2 | 1] = [8, 12, 14, 15].

Input: N = 6, arr[] = [2, 3, 4, 2, 3, 4]
Output : [4, 3, 2, 2, 3, 4]
Explanation: Prefix of the rearranged array is [4, 4 | 3, 4 | 3 | 2, 4 | 3 | 2 | 2, 4 | 3 | 2 | 2 | 3, 4 | 3 | 2 | 2 | 3 | 4] = [4, 7, 7, 7, 7, 7].

Input: N = 2, arr[] = [1, 2]
Output: [2, 1]

Подход:

We can make the observation that only the first log₂(maxval) elements matter, Since after placing them optimally we can be sure that all possible bits that could be set in the prefix OR would have already been set.

So, we can brute force the optimal choice log₂(maxval) times (we choose to add an element if it provides the largest new prefix OR value among all unused elements) and then just add the rest of the unused elements. [maxvalue represents the maximum value in the array].

Следуйте шагам, указанным ниже, чтобы реализовать подход.

• Создайте фиктивный массив (скажем, temp[] ) размера N для хранения окончательного результата.
• Создайте посещаемый массив (скажем , vis[] ) размера N, чтобы проверить, посещался ли элемент ранее или нет, и инициализировать его значением false.
• Инициализируйте переменную cur_or с 0 для вычисления префикса ИЛИ.
• Начните итерацию от min(30, N) до 0 [поскольку можно установить максимум 30 бит].
  • Инициализируйте переменную mx для хранения максимального префикса ИЛИ в каждой позиции, а другую переменную idx — индексом, из которого вычисляется максимальный префикс ИЛИ.
  • Итерируйте от 0 до N и выполните следующую операцию
    • если элемент посещался ранее, пропустите его.
    • если ( cur_or | arr[j] ) больше, чем mx , то обновите (max_or) с помощью ( cur_or | arr[j] ) и обновите idx с помощью j .
  • Обновите vis[idx] с помощью true, temp[k++] с помощью arr[idx] , где k поддерживает индекс, в котором следующий элемент будет помещен во временный массив.
• Поместите оставшиеся непосещенные элементы во временный массив.
• Обновите массив arr[] с помощью temp .

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

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам