Переупорядочить массив, чтобы сделать десятичные эквиваленты обратных двоичных представлений отсортированных элементов массива

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

If the decimal equivalent of reversed binary representations of two or more array elements is equal, then the original value is taken into consideration while rearranging the array.

Примеры:

Input: arr[] = {43, 52, 61, 41}
Output: 52 41 61 43
Explanation:
Below are the reversed binary representation of the array elements:

1. 43 –> (101011)₂ –> reversed –> 53.
2. 52 –> (110100)₂ –> reversed –> 11.
3. 61 –> (111101)₂ –> reversed –> 47.
4. 41 –> (101001)₂ –> reversed –> 37.

Therefore, after rearranging the array element as {52, 41, 61, 43}, the reversed binary representation of rearranged array elements is in sorted order.

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

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

• Инициализируйте массив, скажем, newArr[] , вставьте все элементы массива как обратное двоичное представление числа.
• Отсортируйте массив newArr[] по возрастанию.
• Перейдите массив newArr[] и скопируйте все элементы в массив arr[] .
• Теперь обновите все элементы массива как обратное двоичное представление числа.
• После выполнения вышеуказанных шагов выведите элементы массива arr[] в качестве вывода.

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

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

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

• Объявите функцию, которая принимает элемент массива в качестве параметра и возвращает десятичный эквивалент его обратного двоичного представления.
• Отсортируйте массив, используя функцию в качестве ключа при сортировке.
• Напечатайте элементы массива в качестве вывода.

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

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