Dada una array arr[] , la tarea es generar una array modificada de modo que todos sus elementos se maximicen mediante el intercambio de bits.
Ejemplos:
Entrada: arr[] = {10, 15}
Salida: 12, 15
Explicación:
Representación binaria de (10) 10 = (1010) 2 . Intercambie el segundo y tercer bit para obtener la representación binaria como (1100) 2 = (12) 10 .
Para 15, su representación binaria es 1111, que no se puede cambiar más para obtener un valor mayor.
Entrada: arr[] = {8, 15, 9, 10, 14}
Salida: 8, 15, 12, 12, 14
Enfoque:
siga los pasos a continuación para resolver el problema:
- Cuente el número de bits activados y desactivados en cada elemento de la array.
- Desplace todos los bits establecidos a la izquierda (MSB) y todos los bits no establecidos a la derecha (LSB) para maximizar los elementos de la array.
- Si el recuento de bits activados o desactivados es igual al número de bits del elemento de array, ese elemento no se puede modificar (p. ej., (7) 10 = (111) 2
- Imprime los elementos maximizados en la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to // find maximum sequence by // swapping bits #include <bits/stdc++.h> using namespace std; // Function to generate the maximized // array elements void maximizedArray( int arr[], int N) { int num, i = 0; // Traverse the array while (N--) { num = arr[i]; int one = 0; int zero = 0; // Iterate to count set and // unset bits while (num) { // Count of unset bits if (num % 2 == 0) { zero++; } else { // Count of set bits one++; } // Bitwise right shift num = num >> 1; } for (int j = zero; j < (one + zero); j++) { // Shifting all 1's to MSB // and 0's to LSB num += (1 << j); } cout << num; i++; if (N > 0) cout << ", "; } } // Driver Code int main() { int arr[] = { 8, 15, 9, 10, 14 }; int N = sizeof(arr) / sizeof(arr[0]); maximizedArray( arr, N); return 0; }
Java
// Java implementation to find // maximum sequence by swapping bits class GFG{ // Function to generate the maximized // array elements public static void maximizedArray(int arr[], int N) { int num, i = 0; // Traverse the array for(int l = N; l > 0; l--) { num = arr[i]; int one = 0; int zero = 0; // Iterate to count set and // unset bits while (num != 0) { // Count of unset bits if (num % 2 == 0) { zero++; } else { // Count of set bits one++; } // Bitwise right shift num = num >> 1; } for(int j = zero; j < (one + zero); j++) { // Shifting all 1's to MSB // and 0's to LSB num += (1 << j); } System.out.print(num); i++; if (N > 0) System.out.print(", "); } } // Driver Code public static void main(String args[]) { int arr[] = { 8, 15, 9, 10, 14 }; int N = arr.length; maximizedArray(arr, N); } } // This code is contributed by SoumikMondal
Python3
# Python3 implementation to find # maximum sequence by swapping bits # Function to generate the maximized # array elements def maximizedArray(arr, N): i = 0 # Traverse the array while (N > 0): num = arr[i] one = 0 zero = 0 # Iterate to count set and # unset bits while (num): # Count of unset bits if (num % 2 == 0): zero += 1 else: # Count of set bits one += 1 # Bitwise right shift num = num >> 1 for j in range(zero, (one + zero)): # Shifting all 1's to MSB # and 0's to LSB num += (1 << j) print(num, end = "") i += 1 if (N > 0): print(", ", end = "") N -= 1 # Driver Code if __name__ == "__main__": arr = [ 8, 15, 9, 10, 14 ] N = len(arr) maximizedArray(arr, N) # This code is contributed by chitranayal
C#
// C# implementation to find // maximum sequence by swapping bits using System; class GFG{ // Function to generate the maximized // array elements public static void maximizedArray(int []arr, int N) { int num, i = 0; // Traverse the array for(int l = N; l > 0; l--) { num = arr[i]; int one = 0; int zero = 0; // Iterate to count set and // unset bits while (num != 0) { // Count of unset bits if (num % 2 == 0) { zero++; } else { // Count of set bits one++; } // Bitwise right shift num = num >> 1; } for(int j = zero; j < (one + zero); j++) { // Shifting all 1's to MSB // and 0's to LSB num += (1 << j); } Console.Write(num); i++; if (N > 0) Console.Write(", "); } } // Driver Code public static void Main(String []args) { int []arr = { 8, 15, 9, 10, 14 }; int N = arr.Length; maximizedArray(arr, N); } } // This code is contributed by sapnasingh4991
Javascript
<script> // Javascript implementation to find // maximum sequence by swapping bits // Function to generate the maximized // array elements function maximizedArray(arr, N) { let num, i = 0; // Traverse the array for(let l = N; l > 0; l--) { num = arr[i]; let one = 0; let zero = 0; // Iterate to count set and // unset bits while (num != 0) { // Count of unset bits if (num % 2 == 0) { zero++; } else { // Count of set bits one++; } // Bitwise right shift num = num >> 1; } for(let j = zero; j < (one + zero); j++) { // Shifting all 1's to MSB // and 0's to LSB num += (1 << j); } document.write(num); i++; if (N > 0) document.write(", "); } } // Driver Code let arr = [ 8, 15, 9, 10, 14 ]; let N = arr.length; maximizedArray(arr, N); </script>
8, 15, 12, 12, 14
Complejidad temporal: O(Nlog 2 N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por deepika_sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA