Par mínimo de valores XOR

Dada una array de enteros. Encuentre el par en una array que tenga un valor XOR mínimo. 

Ejemplos: 

Input : arr[] =  {9, 5, 3}
Output : 6
        All pair with xor value (9 ^ 5) => 12, 
        (5 ^ 3) => 6, (9 ^ 3) => 10.
        Minimum XOR value is 6

Input : arr[] = {1, 2, 3, 4, 5}
Output : 1 

Una solución simple es generar todos los pares de la array dada y calcular XOR sus valores. Finalmente, devuelva el valor XOR mínimo. Esta solución toma O(n 2 ) tiempo. 

Implementación:

C++

// C++ program to find minimum XOR value in an array.
#include <bits/stdc++.h>
using namespace std;
 
// Returns minimum xor value of pair in arr[0..n-1]
int minXOR(int arr[], int n)
{
    int min_xor = INT_MAX; // Initialize result
 
    // Generate all pair of given array
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
 
            // update minimum xor value if required
            min_xor = min(min_xor, arr[i] ^ arr[j]);
 
    return min_xor;
}
 
// Driver program
int main()
{
    int arr[] = { 9, 5, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minXOR(arr, n) << endl;
    return 0;
}

Java

// Java program to find minimum XOR value in an array.
class GFG {
 
    // Returns minimum xor value of pair in arr[0..n-1]
    static int minXOR(int arr[], int n)
    {
        int min_xor = Integer.MAX_VALUE; // Initialize result
 
        // Generate all pair of given array
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
 
                // update minimum xor value if required
                min_xor = Math.min(min_xor, arr[i] ^ arr[j]);
 
        return min_xor;
    }
 
    // Driver program
    public static void main(String args[])
    {
        int arr[] = { 9, 5, 3 };
        int n = arr.length;
        System.out.println(minXOR(arr, n));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python program to find minimum
# XOR value in an array.
 
# Function to find minimum XOR pair
def minXOR(arr, n):
     
    # Sort given array
    arr.sort();
 
    min_xor = 999999
    val = 0
 
    # calculate min xor of
    # consecutive pairs
    for i in range (0, n-1):
        for j in range (i+1, n-1):
             
            # update minimum xor value
            # if required
            val = arr[i] ^ arr[j]
            min_xor = min(min_xor, val)
    return min_xor
 
# Driver program
arr = [ 9, 5, 3 ]
n = len(arr)
 
print(minXOR(arr, n))
 
# This code is contributed by Sam007.

C#

// C# program to find minimum
// XOR value in an array.
using System;
 
class GFG {
     
    // Returns minimum xor value of
    // pair in arr[0..n-1]
    static int minXOR(int[] arr, int n)
    {
         // Initialize result
        int min_xor = int.MaxValue;
 
        // Generate all pair of given array
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
 
            // update minimum xor value if required
            min_xor = Math.Min(min_xor, arr[i] ^ arr[j]);
 
        return min_xor;
    }
 
    // Driver program
    public static void Main()
    {
        int[] arr = { 9, 5, 3 };
        int n = arr.Length;
        Console.WriteLine(minXOR(arr, n));
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program to find minimum
// XOR value in an array.
 
// Returns minimum xor value
// of pair in arr[0..n-1]
function minXOR($arr, $n)
{
    // Initialize result
    $min_xor = PHP_INT_MAX;
 
    // Generate all pair of given array
    for ( $i = 0; $i < $n; $i++)
        for ( $j = $i + 1; $j < $n; $j++)
 
            // update minimum xor
            // value if required
            $min_xor = min($min_xor, $arr[$i] ^ $arr[$j]);
 
    return $min_xor;
}
 
    // Driver Code
    $arr = array(9, 5, 3);
    $n = count($arr);
    echo minXOR($arr, $n);
     
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// Javascript program to find
// minimum XOR value in an array.
 
// Returns minimum xor value of pair in arr[0..n-1]
function minXOR(arr, n)
{
    // Initialize result
    let min_xor = Number.MAX_VALUE;
 
    // Generate all pair of given array
    for (let i = 0; i < n; i++)
        for (let j = i + 1; j < n; j++)
 
            // update minimum xor value if required
            min_xor = Math.min(min_xor, arr[i] ^ arr[j]);
 
    return min_xor;
}
 
// Driver program
    let arr = [ 9, 5, 3 ];
    let n = arr.length;
    document.write(minXOR(arr, n));
 
</script>
Producción

6

Una solución eficiente puede resolver este problema en tiempo O(nlogn). 

Algoritmo: 

  1. Ordenar la array dada
  2. Atraviesa y verifica XOR para cada par consecutivo

A continuación se muestra la implementación del enfoque anterior:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum XOR pair
int minXOR(int arr[], int n)
{
    // Sort given array
    sort(arr, arr + n);
 
    int minXor = INT_MAX;
    int val = 0;
 
    // calculate min xor of consecutive pairs
    for (int i = 0; i < n - 1; i++) {
        val = arr[i] ^ arr[i + 1];
        minXor = min(minXor, val);
    }
 
    return minXor;
}
 
// Driver program
int main()
{
    int arr[] = { 9, 5, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minXOR(arr, n) << endl;
 
    return 0;
}

Java

import java.util.Arrays;
class GFG {
 
    // Function to find minimum XOR pair
    static int minXOR(int arr[], int n)
    {
        // Sort given array
        Arrays.parallelSort(arr);
 
        int minXor = Integer.MAX_VALUE;
        int val = 0;
 
        // calculate min xor of consecutive pairs
        for (int i = 0; i < n - 1; i++) {
            val = arr[i] ^ arr[i + 1];
            minXor = Math.min(minXor, val);
        }
 
        return minXor;
    }
 
    // Driver program
    public static void main(String args[])
    {
        int arr[] = { 9, 5, 3 };
        int n = arr.length;
        System.out.println(minXOR(arr, n));
    }
}
 
// This code is contributed by Sumit Ghosh

Python3

import sys   
 
# Function to find minimum XOR pair
def minXOR(arr, n):
     
    # Sort given array
    arr.sort()
  
    minXor =  int(sys.float_info.max)
    val = 0
  
    # calculate min xor of consecutive pairs
    for i in range(0,n-1):
        val = arr[i] ^ arr[i + 1];
        minXor = min(minXor, val);
     
    return minXor
 
# Driver program
arr = [9, 5, 3]
n = len(arr)
print(minXOR(arr, n))
  
# This code is contributed by Sam007.

C#

// C# program to find minimum
// XOR value in an array.
using System;
 
class GFG {
     
    // Function to find minimum XOR pair
    static int minXOR(int[] arr, int n)
    {
        // Sort given array
        Array.Sort(arr);
 
        int minXor = int.MaxValue;
        int val = 0;
 
        // calculate min xor of consecutive pairs
        for (int i = 0; i < n - 1; i++) {
            val = arr[i] ^ arr[i + 1];
            minXor = Math.Min(minXor, val);
        }
 
        return minXor;
    }
 
    // Driver program
    public static void Main()
    {
        int[] arr = { 9, 5, 3 };
        int n = arr.Length;
        Console.WriteLine(minXOR(arr, n));
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// Function to find minimum XOR pair
function minXOR($arr, $n)
{
    // Sort given array
    sort($arr);
 
    $minXor = PHP_INT_MAX;
    $val = 0;
 
    // calculate min xor
    // of consecutive pairs
    for ($i = 0; $i < $n - 1; $i++)
    {
        $val = $arr[$i] ^ $arr[$i + 1];
        $minXor = min($minXor, $val);
    }
 
    return $minXor;
}
 
// Driver Code
$arr = array(9, 5, 3);
$n = count($arr);
echo minXOR($arr, $n);
 
// This code is contributed by Smitha.
?>

Javascript

<script>
 
// Function to find minimum XOR pair
function minXOR(arr, n)
{
    // Sort given array
    arr.sort();
 
    let minXor = Number.MAX_VALUE;
    let val = 0;
 
    // calculate min xor of consecutive pairs
    for (let i = 0; i < n - 1; i++) {
        val = arr[i] ^ arr[i + 1];
        minXor = Math.min(minXor, val);
    }
 
    return minXor;
}
 
// Driver program
    let arr = [ 9, 5, 3 ];
    let n = arr.length;
    document.write(minXOR(arr, n));
 
</script>
Producción

6

Complejidad de tiempo: O(N*logN) 
Complejidad de espacio: O(1) 

Una solución adicional más eficiente puede resolver el problema anterior en tiempo O (n) bajo el supuesto de que los números enteros toman una cantidad fija de bits para almacenar. La idea es utilizar Trie Data Structure.

Algoritmo:

  1. Crea un intento vacío. Cada Node de trie contiene dos hijos para 0 y 1 bits.
  2. Inicialice min_xor = INT_MAX, inserte arr[0] en trie
  3. Recorra todos los elementos de la array uno por uno a partir del segundo.
    1. Primero encuentre el valor mínimo de diferencia de setbet en trie 
      • hacer xor del elemento actual con la mínima diferencia de bit establecido ese valor 
    2. actualice el valor min_xor si es necesario
    3. inserte el elemento de array actual en trie 
  4. volver min_xor

A continuación se muestra la implementación del algoritmo anterior.

C++

// C++ program to find minimum XOR value in an array.
#include <bits/stdc++.h>
using namespace std;
#define INT_SIZE 32
 
// A Trie Node
struct TrieNode {
    int value; // used in leaf node
    TrieNode* Child[2];
};
 
// Utility function to create a new Trie node
TrieNode* getNode()
{
    TrieNode* newNode = new TrieNode;
    newNode->value = 0;
    newNode->Child[0] = newNode->Child[1] = NULL;
    return newNode;
}
 
// utility function insert new key in trie
void insert(TrieNode* root, int key)
{
    TrieNode* temp = root;
 
    // start from the most significant bit, insert all
    // bit of key one-by-one into trie
    for (int i = INT_SIZE - 1; i >= 0; i--) {
        // Find current bit in given prefix
        bool current_bit = (key & (1 << i));
 
        // Add a new Node into trie
        if (temp->Child[current_bit] == NULL)
            temp->Child[current_bit] = getNode();
 
        temp = temp->Child[current_bit];
    }
 
    // store value at leafNode
    temp->value = key;
}
 
// Returns minimum XOR value of an integer inserted
// in Trie and given key.
int minXORUtil(TrieNode* root, int key)
{
    TrieNode* temp = root;
 
    for (int i = INT_SIZE - 1; i >= 0; i--) {
        // Find current bit in given prefix
        bool current_bit = (key & (1 << i));
 
        // Traversal Trie, look for prefix that has
        // same bit
        if (temp->Child[current_bit] != NULL)
            temp = temp->Child[current_bit];
 
        // if there is no same bit.then looking for
        // opposite bit
        else if (temp->Child[1 - current_bit] != NULL)
            temp = temp->Child[1 - current_bit];
    }
 
    // return xor value of minimum bit difference value
    // so we get minimum xor value
    return key ^ temp->value;
}
 
// Returns minimum xor value of pair in arr[0..n-1]
int minXOR(int arr[], int n)
{
    int min_xor = INT_MAX; // Initialize result
 
    // create a True and insert first element in it
    TrieNode* root = getNode();
    insert(root, arr[0]);
 
    // Traverse all array element and find minimum xor
    // for every element
    for (int i = 1; i < n; i++) {
        // Find minimum XOR value of current element with
        // previous elements inserted in Trie
        min_xor = min(min_xor, minXORUtil(root, arr[i]));
 
        // insert current array value into Trie
        insert(root, arr[i]);
    }
    return min_xor;
}
 
// Driver code
int main()
{
    int arr[] = { 9, 5, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minXOR(arr, n) << endl;
    return 0;
}

Java

// Java program to find minimum XOR value in an array.
class GFG {
    static final int INT_SIZE = 32;
 
    // A Trie Node
    static class TrieNode {
        int value; // used in leaf node
        TrieNode[] Child = new TrieNode[2];
 
        public TrieNode()
        {
            value = 0;
            Child[0] = null;
            Child[1] = null;
        }
    }
    static TrieNode root;
 
    // utility function insert new key in trie
    static void insert(int key)
    {
        TrieNode temp = root;
 
        // start from the most significant bit, insert all
        // bit of key one-by-one into trie
        for (int i = INT_SIZE - 1; i >= 0; i--) {
            // Find current bit in given prefix
            int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;
 
            // Add a new Node into trie
            if (temp != null && temp.Child[current_bit] == null)
                temp.Child[current_bit] = new TrieNode();
 
            temp = temp.Child[current_bit];
        }
 
        // store value at leafNode
        temp.value = key;
    }
 
    // Returns minimum XOR value of an integer inserted
    // in Trie and given key.
    static int minXORUtil(int key)
    {
        TrieNode temp = root;
 
        for (int i = INT_SIZE - 1; i >= 0; i--) {
            // Find current bit in given prefix
            int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;
 
            // Traversal Trie, look for prefix that has
            // same bit
            if (temp.Child[current_bit] != null)
                temp = temp.Child[current_bit];
 
            // if there is no same bit.then looking for
            // opposite bit
            else if (temp.Child[1 - current_bit] != null)
                temp = temp.Child[1 - current_bit];
        }
 
        // return xor value of minimum bit difference value
        // so we get minimum xor value
        return key ^ temp.value;
    }
 
    // Returns minimum xor value of pair in arr[0..n-1]
    static int minXOR(int arr[], int n)
    {
        int min_xor = Integer.MAX_VALUE; // Initialize result
 
        // create a True and insert first element in it
        root = new TrieNode();
        insert(arr[0]);
 
        // Traverse all array element and find minimum xor
        // for every element
        for (int i = 1; i < n; i++) {
            // Find minimum XOR value of current element with
            // previous elements inserted in Trie
            min_xor = Math.min(min_xor, minXORUtil(arr[i]));
 
            // insert current array value into Trie
            insert(arr[i]);
        }
        return min_xor;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 9, 5, 3 };
        int n = arr.length;
        System.out.println(minXOR(arr, n));
    }
}
// This code is contributed by Sumit Ghosh

Python

# class for the basic Trie Node
class TrieNode:
    def __init__(self):
 
        # Child array with 0 and 1
        self.child = [None]*2
 
        # meant for the lead Node
        self.value = None
 
class Trie:
 
    def __init__(self):
        # initialise the root Node
        self.root = self.getNode()
 
    def getNode(self):
        # get a new Trie Node
        return TrieNode()
 
    # inserts a new element
    def insert(self,key):
        temp = self.root
  
        # 32 bit valued binary digit
        for i in range(31,-1,-1):
 
            # finding the bit at ith position
            curr = (key>>i)&(1)
 
            # if the child is None create one
            if(temp.child[curr] is None):
                temp.child[curr] = self.getNode()
            temp = temp.child[curr]
 
        # add value to the leaf node
        temp.value = key
 
    # traverse the trie and xor with the most similar element
    def xorUtil(self,key):
        temp = self.root
 
        # 32 bit valued binary digit
        for i in range(31,-1,-1):
 
            # finding the bit at ith position
            curr = (key>>i)&1
 
            # traverse for the same bit
            if(temp.child[curr] is not None):
                temp = temp.child[curr]
 
            # traverse if the same bit is not set in trie
            else if(temp.child[1-curr] is not None):
                temp = temp.child[1-curr]
 
        # return with the xor of the value
        return temp.value^key
             
         
def minXor(arr):
 
        # set m to a large number
        m = 2**30
 
        # initialize Trie
        trie = Trie()
 
        # insert the first element
        trie.insert(arr[0])
 
        # for each element in the array
        for i in range(1,len(arr)):
 
            # find the minimum xor value
            m = min(m,trie.xorUtil(arr[i]))
             
            # insert the new element
            trie.insert(arr[i])
        return m
 
# Driver Code
if __name__=="__main__":
    sample = [9,5,3]
    print(minXor(sample))
 
#code contributed by Ashwin Bhat   
Producción

6

Tiempo Complejidad O(n)

Este artículo es una contribución de Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *