Dada una array arr[] que consta de N enteros positivos, la tarea es reorganizar la array de manera que se ordene la representación binaria inversa de todos los elementos de la array .
Si el equivalente decimal de las representaciones binarias invertidas de dos o más elementos de la array es igual, se tiene en cuenta el valor original al reorganizar la array.
Ejemplos:
Entrada: arr[] = {43, 52, 61, 41}
Salida: 52 41 61 43
Explicación:
A continuación se muestra la representación binaria inversa de los elementos de la array:
- 43 –> (101011) 2 –> invertido –> 53.
- 52 –> (110100) 2 –> invertido –> 11.
- 61 –> (111101) 2 –> invertido –> 47.
- 41 –> (101001) 2 –> invertido –> 37.
Por lo tanto, después de reorganizar el elemento de la array como {52, 41, 61, 43}, la representación binaria inversa de los elementos de la array reorganizados está ordenada.
Entrada: arr[] = {5, 3, 6, 2, 4}
Salida: 2 4 3 6 5
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos newArr[] , inserte todos los elementos de la array como la representación binaria inversa del número.
- Ordene la array newArr[] en orden creciente.
- Recorra la array newArr[] y copie todos los elementos en la array arr[] .
- Ahora, actualice todos los elementos de la array como la representación binaria invertida del número .
- Después de completar los pasos anteriores, imprima los elementos de la array arr[] como salida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to reverse the bits of a number int keyFunc(int n) { // Stores the reversed number int rev = 0; while (n > 0) { // Divide rev by 2 rev = rev << 1; // If the value of N is odd if (n & 1 == 1) rev = rev ^ 1; // Update the value of N n = n >> 1; } // Return the final value of rev return rev; } // Function for rearranging the array // element according to the given rules vector<vector<int>> getNew(vector<int> arr) { // Stores the new array elements vector<vector<int>> ans; for (int i:arr) ans.push_back({keyFunc(i), i}); return ans; } // Function for rearranging the array vector<int> getArr(vector<vector<int> > arr){ // Stores the new array vector<int> ans; for (auto i:arr) ans.push_back(i[1]); return ans; } // Function to sort the array by reversing // binary representation void sortArray(vector<int> arr) { // Creating a new array vector<vector<int> > newArr = getNew(arr); // Sort the array with the key sort(newArr.begin(),newArr.end()); // Get arr from newArr arr = getArr(newArr); // Print the sorted array int n = arr.size(); cout<<"["; for(int i = 0; i < n - 1; i++) cout << arr[i] << ", "; cout << arr[n - 1] << "]"; } // Driver Code int main() { vector<int> arr = {43, 52, 61, 41}; sortArray(arr); return 0; } // This code is contributed by mohit kumar 29.
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to reverse the bits of a number static int keyFunc(int n) { // Stores the reversed number int rev = 0; while (n > 0) { // Divide rev by 2 rev = rev << 1; // If the value of N is odd if ((n & 1) == 1) rev = rev ^ 1; // Update the value of N n = n >> 1; } // Return the final value of rev return rev; } // Function for rearranging the array // element according to the given rules static int[][] getNew(int arr[]) { // Stores the new array elements int ans[][] = new int[arr.length][2]; for(int i = 0; i < arr.length; i++) ans[i] = new int[]{ keyFunc(arr[i]), arr[i] }; return ans; } // Function for rearranging the array static int[] getArr(int[][] arr) { // Stores the new array int ans[] = new int[arr.length]; int idx = 0; for(int i[] : arr) ans[idx++] = i[1]; return ans; } // Function to sort the array by reversing // binary representation static void sortArray(int arr[]) { // Creating a new array int[][] newArr = getNew(arr); // Sort the array with the key Arrays.sort(newArr, (a, b) -> { if (Integer.compare(a[0], b[0]) == 0) return Integer.compare(a[1], b[1]); return Integer.compare(a[0], b[0]); }); // Get arr from newArr arr = getArr(newArr); // Print the sorted array int n = arr.length; System.out.print("["); for(int i = 0; i < n - 1; i++) System.out.print(arr[i] + ", "); System.out.print(arr[n - 1] + "]"); } // Driver Code public static void main(String[] args) { int arr[] = { 43, 52, 61, 41 }; sortArray(arr); } } // This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to reverse the bits of a number def keyFunc(n): # Stores the reversed number rev = 0 while (n > 0): # Divide rev by 2 rev = rev << 1 # If the value of N is odd if (n & 1 == 1): rev = rev ^ 1 # Update the value of N n = n >> 1 # Return the final value of rev return rev # Function for rearranging the array # element according to the given rules def getNew(arr): # Stores the new array elements ans = [] for i in arr: ans.append([keyFunc(i), i]) return ans # Function for rearranging the array def getArr(arr): # Stores the new array ans = [] for i in arr: ans.append(i[1]) return ans # Function to sort the array by reversing # the binary representation def sortArray(arr): # Creating a new array newArr = getNew(arr) # Sort the array with the key newArr.sort() # Get arr from newArr arr = getArr(newArr) # Print the sorted array print(arr) # Driver Code arr = [43, 52, 61, 41] sortArray(arr)
C#
// C# program for the above approach using System; class GFG { // Function to reverse the bits of a number static int keyFunc(int n) { // Stores the reversed number int rev = 0; while (n > 0) { // Divide rev by 2 rev = rev << 1; // If the value of N is odd if ((n & 1) == 1) rev = rev ^ 1; // Update the value of N n = n >> 1; } // Return the final value of rev return rev; } // Function for rearranging the array // element according to the given rules static int[][] getNew(int[] arr) { // Stores the new array elements int[][] ans = new int[arr.Length][]; for (int i = 0; i < arr.Length; i++) ans[i] = new int[] { keyFunc(arr[i]), arr[i] }; return ans; } // Function for rearranging the array static int[] getArr(int[][] arr) { // Stores the new array int[] ans = new int[arr.Length]; int idx = 0; foreach(var i in arr) ans[idx++] = i[1]; return ans; } // Function to sort the array by reversing // binary representation static void sortArray(int[] arr) { // Creating a new array int[][] newArr = getNew(arr); // Sort the array with the key Array.Sort( newArr, new Comparison<int[]>((a, b) => { return (a[0] == b[0]) ? (a[1] - b[1]) : (a[0] - b[0]); })); // Get arr from newArr arr = getArr(newArr); // Print the sorted array int n = arr.Length; Console.Write("["); for (int i = 0; i < n - 1; i++) Console.Write(arr[i] + ", "); Console.Write(arr[n - 1] + "]"); } // Driver Code public static void Main(string[] args) { int[] arr = { 43, 52, 61, 41 }; sortArray(arr); } } // This code is contributed by phasing17
Javascript
<script> // JavaScript program for the above approach // Function to reverse the bits of a number function keyFunc(n) { // Stores the reversed number let rev = 0; while (n > 0) { // Divide rev by 2 rev = rev << 1; // If the value of N is odd if (n & 1 == 1) rev = rev ^ 1; // Update the value of N n = n >> 1; } // Return the final value of rev return rev; } // Function for rearranging the array // element according to the given rules function getNew(arr) { // Stores the new array elements let ans = []; for (let i of arr) ans.push([keyFunc(i), i]); return ans; } // Function for rearranging the array function getArr(arr) { // Stores the new array let ans = []; for (let i of arr) ans.push(i[1]); return ans; } // Function to sort the array by reversing // binary representation function sortArray(arr) { // Creating a new array let newArr = getNew(arr); // Sort the array with the key newArr.sort(); // Get arr from newArr arr = getArr(newArr); // Print the sorted array let n = arr.length; document.write("["); for (let i = 0; i < n - 1; i++) document.write(arr[i] + ", "); document.write(arr[n - 1] + "]"); } // Driver Code let arr = [43, 52, 61, 41]; sortArray(arr); // This code is contributed by _saurabh_jaiswal </script>
[52, 41, 61, 43]
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Enfoque optimizado para el espacio: siga los pasos a continuación para resolver el problema:
- Declare una función para aceptar un elemento de array como parámetro y devuelva el equivalente decimal de su representación binaria invertida.
- Ordene la array usando la función como clave mientras ordena.
- Imprime los elementos de la array como salida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to reverse the bits of number int keyFunc(int n) { // Stores the reversed number int rev = 0; while (n > 0) { // Divide rev by 2 rev = rev << 1; // If the value of N is odd if (n & 1 == 1) rev = rev ^ 1; // Update the value of N n = n >> 1; } // Return the final value of rev return rev; } //defining the comparison function bool compare(int a, int b) { return keyFunc(a) < keyFunc(b); } // Function to sort the array by reversing // binary representation void sortArray(int arr[], int n) { // Sort the array with the key sort(arr, arr + n, compare); // Print the sorted array for (int i = 0; i < n; i++) cout << arr[i] << " "; } int main() { // Driver Code int arr[] = { 43, 52, 61, 41 }; int n = 4; sortArray(arr, n); return 0; } // this code is contributed by phasing17
Python3
# Python3 program for the above approach # Function to reverse the bits of number def keyFunc(n): # Stores the reversed number rev = 0 while (n > 0): # Divide rev by 2 rev = rev << 1 # If the value of N is odd if (n & 1 == 1): rev = rev ^ 1 # Update the value of N n = n >> 1 # Return the final value of rev return rev # Function to sort the array by reversing # binary representation def sortArray(arr): # Sort the array with the key arr = sorted(arr, key = keyFunc) # Print the sorted array print(arr) # Driver Code arr = [43, 52, 61, 41] sortArray(arr)
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to reverse the bits of number public static int keyFunc(int n) { // Stores the reversed number int rev = 0; while (n > 0) { // Divide rev by 2 rev = rev << 1; // If the value of N is odd if ((n & 1) == 1) rev = rev ^ 1; // Update the value of N n = n >> 1; } // Return the final value of rev return rev; } // defining the comparison function public static int compare(int a, int b) { return keyFunc(a) - keyFunc(b); } // Function to sort the array by reversing // binary representation public static void sortArray(int[] arr, int n) { // Sort the array with the key Array.Sort(arr, compare); // Print the sorted array for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } public static void Main(string[] args) { // Driver Code int[] arr = { 43, 52, 61, 41 }; int n = 4; sortArray(arr, n); } } // This code is contributed by phasing17
Javascript
// JavaScript program for the above approach // Function to reverse the bits of number function keyFunc(n) { // Stores the reversed number var rev = 0; while (n > 0) { // Divide rev by 2 rev = rev << 1; // If the value of N is odd if (n & 1 == 1) rev = rev ^ 1; // Update the value of N n = n >> 1; } // Return the final value of rev return rev; } // Function to sort the array by reversing // binary representation function sortArray(arr) { // Sort the array with the key arr.sort((a, b) => keyFunc(a) > keyFunc(b)); // Print the sorted array console.log(arr); } // Driver Code var arr = [43, 52, 61, 41]; sortArray(arr); //this code is contributed by phasing17
[52, 41, 61, 43]
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA