Partición de array en dos subconjuntos con mínimo Bitwise XOR entre su máximo y mínimo

Dada una array arr[] de tamaño N , la tarea es dividir la array en dos subconjuntos de modo que Bitwise XOR entre el máximo del primer subconjunto y el mínimo del segundo subconjunto sea mínimo.

Ejemplos:

Entrada: arr[] = {3, 1, 2, 6, 4} 
Salida: 1 
Explicación: 
Dividir la array dada en dos subconjuntos {1, 3}, {2, 4, 6}. 
El máximo del primer subconjunto es 3 y el mínimo del segundo subconjunto es 2. 
Por lo tanto, su XOR bit a bit es igual a 1.

Entrada: arr[] = {2, 1, 3, 2, 4, 3} 
Salida: 0

Enfoque: la idea es encontrar los dos elementos en la array de modo que el XOR bit a bit entre los dos elementos de la array sea mínimo. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos minXOR , para almacenar el valor mínimo posible de Bitwise XOR entre el elemento máximo de un subconjunto y el elemento mínimo del otro subconjunto.
• Ordene la array arr[] en orden ascendente .
• Recorra la array y actualice minXOR = min(minXOR, arr[i] ^ arr[i – 1]) .

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 split the array into two subset
// such that the Bitwise XOR between the maximum
// of one subset and minimum of other is minimum
int splitArray(int arr[], int N)
{
    // Sort the array in
    // increasing order
    sort(arr, arr + N);
 
    int result = INT_MAX;
 
    // Calculating the min Bitwise XOR
    // between consecutive elements
    for (int i = 1; i < N; i++) {
        result = min(result,
                     arr[i] - arr[i - 1]);
    }
 
    // Return the final
    // minimum Bitwise XOR
    return result;
}
 
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 3, 1, 2, 6, 4 };
 
    // Size of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << splitArray(arr, N);
    return 0;
}

// java program for the above approach
import java.util.*;
class GFG{
 
// Function to split the array into two subset
// such that the Bitwise XOR between the maximum
// of one subset and minimum of other is minimum
static int splitArray(int arr[], int N)
{
    // Sort the array in
    // increasing order
    Arrays.sort(arr);
 
    int result = Integer.MAX_VALUE;
 
    // Calculating the min Bitwise XOR
    // between consecutive elements
    for (int i = 1; i < N; i++)
    {
        result = Math.min(result,
                          arr[i] - arr[i - 1]);
    }
 
    // Return the final
    // minimum Bitwise XOR
    return result;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array arr[]
    int arr[] = { 3, 1, 2, 6, 4 };
 
    // Size of array
    int N = arr.length;
 
    // Function Call
    System.out.print(splitArray(arr, N));
}
}

# Python3 program for the above approach
 
# Function to split the array into two subset
# such that the Bitwise XOR between the maximum
# of one subset and minimum of other is minimum
def splitArray(arr, N):
     
    # Sort the array in increasing
    # order
    arr = sorted(arr)
 
    result = 10 ** 9
 
    # Calculating the min Bitwise XOR
    # between consecutive elements
    for i in range(1, N):
        result = min(result, arr[i] ^ arr[i - 1])
 
    # Return the final
    # minimum Bitwise XOR
    return result
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 3, 1, 2, 6, 4 ]
 
    # Size of array
    N = len(arr)
 
    # Function Call
    print(splitArray(arr, N))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG{
 
// Function to split the array into two subset
// such that the Bitwise XOR between the maximum
// of one subset and minimum of other is minimum
static int splitArray(int []arr, int N)
{
    // Sort the array in increasing order
    Array.Sort(arr);
 
    int result = Int32.MaxValue;
 
    // Calculating the min Bitwise XOR
    // between consecutive elements
    for (int i = 1; i < N; i++)
    {
        result = Math.Min(result,
                          arr[i] ^ arr[i - 1]);
    }
 
    // Return the final
    // minimum Bitwise XOR
    return result;
}
 
// Driver Code
public static void Main()
{
    // Given array arr[]
    int []arr = { 3, 1, 2, 6, 4 };
 
    // Size of array
    int N = arr.Length;
 
    // Function Call
    Console.Write(splitArray(arr, N));
}
}

<script>
 
// Javascript program for the above approach
 
// Function to split the array into two subset
// such that the Bitwise XOR between the maximum
// of one subset and minimum of other is minimum
function splitArray(arr, N)
{
    // Sort the array in
    // increasing order
    arr.sort();
 
    let result = Number.MAX_VALUE;
 
    // Calculating the min Bitwise XOR
    // between consecutive elements
    for (let i = 1; i < N; i++) {
        result = Math.min(result,
                     arr[i] - arr[i - 1]);
    }
 
    // Return the final
    // minimum Bitwise XOR
    return result;
}
 
 
// Driver Code
    // Given array arr[]
    let arr = [ 3, 1, 2, 6, 4 ];
 
    // Size of array
    let N = arr.length;
 
    // Function Call
    document.write(splitArray(arr, N));
 
</script>

1

Complejidad de tiempo: O(N * log N)  
Espacio auxiliar: O(1)