XOR mínimo de OR y AND de cualquier par en el Array

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++ 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 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 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# 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

<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)