Dada una array arr[] de N enteros positivos, la tarea es encontrar el valor mínimo de Bitwise XOR de Bitwise OR y AND de cualquier par en la array dada.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 1
Explicación:
Para los elementos 2 y 3:
el valor de la expresión (2 y 3) xor (2|3) es 1, que es el mínimo de todos los pares en la array dada.
Entrada: arr[] = {3, 6, 8, 4, 5}
Salida: 1
Explicación:
para los elementos 4 y 5:
el valor de la expresión (4 y 5) xor (4|5) es 1, que es el mínimo de todos los pares en la array dada.
Enfoque: para cualquier par de elementos, digamos X e Y , el valor de la expresión (X&Y) xor (X|Y) se puede escribir como:
=> (XY)^(X+Y)
=> (XY)(X+Y)’ + (XY)'(X+Y)
=> (XY)(X’.Y’) + (X’+Y ‘)(X+Y)
=> X.X’.Y.Y’ + X’.X + X’.Y + Y’.X + Y’.Y
=> 0 + 0 + X’.Y + Y’. X + 0
=> X^Y
De los cálculos anteriores, para cualquier par (X, Y) en la array dada, la expresión (X&Y) xor (X|Y) se reduce a X xor Y . Por lo tanto, el valor mínimo de Bitwise XOR de Bitwise OR y AND de cualquier par en la array dada recibe XOR del par de valor mínimo que se puede calcular usando el enfoque discutido en este artículo.
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 find the minimum // value of XOR of AND and OR of // any pair in the given array int maxAndXor(int arr[], int n) { int ans = INT_MAX; // Sort the array sort(arr, arr + n); // Traverse the array arr[] for (int i = 0; i < n - 1; i++) { // Compare and Find the minimum // XOR value of an array. ans = min(ans, arr[i] ^ arr[i + 1]); } // Return the final answer return ans; } // Driver Code int main() { // Given array int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << maxAndXor(arr, N); return 0; }
Java
// Java program to for above approach import java.io.*; import java.util.Arrays; class GFG { // Function to find the minimum // value of XOR of AND and OR of // any pair in the given array static int maxAndXor(int arr[], int n) { int ans = Integer.MAX_VALUE; // Sort the array Arrays.sort(arr); // Traverse the array arr[] for (int i = 0; i < n - 1; i++) { // Compare and Find the minimum // XOR value of an array. ans = Math.min(ans, arr[i] ^ arr[i + 1]); } // Return the final answer return ans; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = new int[] { 1, 2, 3, 4, 5 }; int N = arr.length; // Function Call System.out.println(maxAndXor(arr, N)); } } // This code is contributed by Shubham Prakash
Python3
# Python3 program for the above approach # Function to find the minimum # value of XOR of AND and OR of # any pair in the given array def maxAndXor(arr, n): ans = float('inf') # Sort the array arr.sort() # Traverse the array arr[] for i in range(n - 1): # Compare and Find the minimum # XOR value of an array. ans = min(ans, arr[i] ^ arr[i + 1]) # Return the final answer return ans # Driver Code if __name__ == '__main__': # Given array arr = [1, 2, 3, 4, 5] N = len(arr) # Function Call print(maxAndXor(arr, N)) # This code is contributed by Shivam Singh
C#
// C# program to for above approach using System; class GFG { // Function to find the minimum // value of XOR of AND and OR of // any pair in the given array static int maxAndXor(int[] arr, int n) { int ans = 9999999; // Sort the array Array.Sort(arr); // Traverse the array arr[] for (int i = 0; i < n - 1; i++) { // Compare and Find the minimum // XOR value of an array. ans = Math.Min(ans, arr[i] ^ arr[i + 1]); } // Return the final answer return ans; } // Driver Code public static void Main() { // Given array arr[] int[] arr = new int[] { 1, 2, 3, 4, 5 }; int N = arr.Length; // Function Call Console.Write(maxAndXor(arr, N)); } } // This code is contributed by Code_Mech
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum // value of XOR of AND and OR of // any pair in the given array function maxAndXor(arr, n) { let ans = Number.MAX_VALUE; // Sort the array arr.sort(); // Traverse the array arr[] for (let i = 0; i < n - 1; i++) { // Compare and Find the minimum // XOR value of an array. ans = Math.min(ans, arr[i] ^ arr[i + 1]); } // Return the final answer return ans; } // Driver Code // Given array arr[] let arr = [ 1, 2, 3, 4, 5 ]; let N = arr.length; // Function Call document.write(maxAndXor(arr, N)); // This code is contributed by sanjoy_62. </script>
1
Complejidad de tiempo: O(N*log 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