Dada una array arr[] de N enteros positivos, la tarea es encontrar una disposición tal que Bitwise AND de los primeros N – 1 elementos sea igual al último elemento. Si tal disposición no es posible, la salida será -1 .
Ejemplos:
Entrada: arr[] = {1, 5, 3, 3}
Salida: 3 5 3 1
(3 & 5 & 3) = 1 que es igual al último elemento.
Entrada: arr[] = {2, 3, 7}
Salida: -1
No es posible tal arreglo.
Acercarse:
- Sea p = x & y , entonces p ≤ min(x, y) lo que significa que Bitwise AND es una función no creciente. Si se realiza AND bit a bit en algunos elementos, el valor disminuirá o permanecerá igual.
- Por lo tanto, es obvio colocar el elemento más pequeño en el último índice y luego verificar si el último elemento es igual al AND bit a bit de los primeros N – 1 elementos o no. En caso afirmativo, imprima el arreglo requerido; de lo contrario, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Utility function to print // the elements of an array void printArr(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } // Function to find the required arrangement void findArrangement(int arr[], int n) { // There has to be atleast 2 elements if (n < 2) { cout << "-1"; return; } // Minimum element from the array int minVal = *min_element(arr, arr + n); // Swap any occurrence of the minimum // element with the last element for (int i = 0; i < n; i++) { if (arr[i] == minVal) { swap(arr[i], arr[n - 1]); break; } } // Find the bitwise AND of the // first (n - 1) elements int andVal = arr[0]; for (int i = 1; i < n - 1; i++) { andVal &= arr[i]; } // If the bitwise AND is equal // to the last element then // print the arrangement if (andVal == arr[n - 1]) printArr(arr, n); else cout << "-1"; } // Driver code int main() { int arr[] = { 1, 5, 3, 3 }; int n = sizeof(arr) / sizeof(int); findArrangement(arr, n); return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { // Utility function to print // the elements of an array static void printArr(int []arr, int n) { for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } // Function to find the required arrangement static void findArrangement(int arr[], int n) { // There has to be atleast 2 elements if (n < 2) { System.out.print("-1"); return; } // Minimum element from the array int minVal = Arrays.stream(arr).min().getAsInt(); // Swap any occurrence of the minimum // element with the last element for (int i = 0; i < n; i++) { if (arr[i] == minVal) { swap(arr, i, n - 1); break; } } // Find the bitwise AND of the // first (n - 1) elements int andVal = arr[0]; for (int i = 1; i < n - 1; i++) { andVal &= arr[i]; } // If the bitwise AND is equal // to the last element then // print the arrangement if (andVal == arr[n - 1]) printArr(arr, n); else System.out.print("-1"); } static int[] swap(int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void main(String []args) { int arr[] = { 1, 5, 3, 3 }; int n = arr.length; findArrangement(arr, n); } } // This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Utility function to print # the elements of an array def printArr(arr, n) : for i in range(n) : print(arr[i], end = " "); # Function to find the required arrangement def findArrangement(arr, n) : # There has to be atleast 2 elements if (n < 2) : print("-1", end = ""); return; # Minimum element from the array minVal = min(arr); # Swap any occurrence of the minimum # element with the last element for i in range(n) : if (arr[i] == minVal) : arr[i], arr[n - 1] = arr[n - 1], arr[i]; break; # Find the bitwise AND of the # first (n - 1) elements andVal = arr[0]; for i in range(1, n - 1) : andVal &= arr[i]; # If the bitwise AND is equal # to the last element then # print the arrangement if (andVal == arr[n - 1]) : printArr(arr, n); else : print("-1"); # Driver code if __name__ == "__main__" : arr = [ 1, 5, 3, 3 ]; n = len(arr); findArrangement(arr, n); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; using System.Linq; class GFG { // Utility function to print // the elements of an array static void printArr(int []arr, int n) { for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } // Function to find the required arrangement static void findArrangement(int []arr, int n) { // There has to be atleast 2 elements if (n < 2) { Console.Write("-1"); return; } // Minimum element from the array int minVal = arr.Min(); // Swap any occurrence of the minimum // element with the last element for (int i = 0; i < n; i++) { if (arr[i] == minVal) { swap(arr, i, n - 1); break; } } // Find the bitwise AND of the // first (n - 1) elements int andVal = arr[0]; for (int i = 1; i < n - 1; i++) { andVal &= arr[i]; } // If the bitwise AND is equal // to the last element then // print the arrangement if (andVal == arr[n - 1]) printArr(arr, n); else Console.Write("-1"); } static int[] swap(int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void Main(String []args) { int []arr = { 1, 5, 3, 3 }; int n = arr.Length; findArrangement(arr, n); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript implementation of the approach // Utility function to print // the elements of an array function printArr(arr, n) { for (var i = 0; i < n; i++) document.write( arr[i] + " "); } // Function to find the required arrangement function findArrangement(arr, n) { // There has to be atleast 2 elements if (n < 2) { document.write( "-1"); return; } // Minimum element from the array var minVal = arr.reduce((a,b)=> Math.min(a,b)); // Swap any occurrence of the minimum // element with the last element for (var i = 0; i < n; i++) { if (arr[i] == minVal) { [arr[i], arr[n-1]] = [arr[n-1], arr[i]]; break; } } // Find the bitwise AND of the // first (n - 1) elements var andVal = arr[0]; for (var i = 1; i < n - 1; i++) { andVal &= arr[i]; } // If the bitwise AND is equal // to the last element then // print the arrangement if (andVal == arr[n - 1]) printArr(arr, n); else document.write( "-1"); } // Driver code var arr = [1, 5, 3, 3]; var n = arr.length; findArrangement(arr, n); // This code is contributed by rrrtnx. </script>
Producción:
3 5 3 1
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)