Dada una array A que consta de N enteros no negativos, la tarea es elegir un entero K tal que se minimice el máximo de los valores xor de K con todos los elementos de la array. En otras palabras, encuentre el valor mínimo posible de Z, donde Z = max(A[i] xor K) , 0 <= i <= n-1, para algún valor de K.
Ejemplos:
Entrada: A = [1, 2, 3]
Salida: 2
Explicación:
Al elegir K = 3, max(A[i] xor 3) = 2, y este es el valor mínimo posible.
Entrada: A = [3, 2, 5, 6]
Salida: 5
Planteamiento: Para resolver el problema mencionado anteriormente utilizaremos la recursividad . Comenzaremos desde el bit más significativo en la función recursiva.
- En el paso recursivo, divida el elemento en dos secciones: una con el bit actual activado y la otra con el bit actual desactivado. Si alguna de las secciones no tiene un solo elemento, entonces este bit en particular para K se puede elegir de tal manera que el valor xor final tenga 0 en esta posición de bit (dado que nuestro objetivo es minimizar este valor) y luego continuar con el siguiente bit en el siguiente paso recursivo.
- Si ambas secciones tienen algunos elementos, explore ambas posibilidades colocando 0 y 1 en esta posición de bit y calculando la respuesta usando la sección correspondiente en la próxima llamada recursiva.
Sea answer_on el valor si se coloca 1 y answer_off el valor si se coloca 0 en esta posición (pos). Dado que ambas secciones no están vacías, independientemente del bit que elijamos para K, se agregarán 2 pos al valor final.
Para cada paso recursivo:
respuesta = min(respuesta_activada, respuesta_desactivada) + 2 posiciones
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find Minimum
// possible value of the maximum xor
// in an array by choosing some integer
#include <bits/stdc++.h>
using namespace std;
// Function to calculate Minimum possible
// value of the Maximum XOR in an array
int calculate(vector<int>& section, int pos)
{
// base case
if (pos < 0)
return 0;
// Divide elements into two sections
vector<int> on_section, off_section;
// Traverse all elements of current
// section and divide in two groups
for (auto el : section) {
if (((el >> pos) & 1) == 0)
off_section.push_back(el);
else
on_section.push_back(el);
}
// Check if one of the sections is empty
if (off_section.size() == 0)
return calculate(on_section, pos - 1);
if (on_section.size() == 0)
return calculate(off_section, pos - 1);
// explore both the possibilities using recursion
return min(calculate(off_section, pos - 1),
calculate(on_section, pos - 1))
+ (1 << pos);
}
// Function to calculate minimum XOR value
int minXorValue(int a[], int n)
{
vector<int> section;
for (int i = 0; i < n; i++)
section.push_back(a[i]);
// Start recursion from the
// most significant pos position
return calculate(section, 30);
}
// Driver code
int main()
{
int N = 4;
int A[N] = { 3, 2, 5, 6 };
cout << minXorValue(A, N);
return 0;
}
Java
// Java implementation to find Minimum
// possible value of the maximum xor
// in an array by choosing some integer
import java.util.*;
class GFG{
// Function to calculate Minimum possible
// value of the Maximum XOR in an array
static int calculate(Vector<Integer> section, int pos)
{
// Base case
if (pos < 0)
return 0;
// Divide elements into two sections
Vector<Integer> on_section = new Vector<Integer>(),
off_section = new Vector<Integer>();
// Traverse all elements of current
// section and divide in two groups
for(int el : section)
{
if (((el >> pos) & 1) == 0)
off_section.add(el);
else
on_section.add(el);
}
// Check if one of the sections is empty
if (off_section.size() == 0)
return calculate(on_section, pos - 1);
if (on_section.size() == 0)
return calculate(off_section, pos - 1);
// Explore both the possibilities using recursion
return Math.min(calculate(off_section, pos - 1),
calculate(on_section, pos - 1)) +
(1 << pos);
}
// Function to calculate minimum XOR value
static int minXorValue(int a[], int n)
{
Vector<Integer> section = new Vector<Integer>();
for(int i = 0; i < n; i++)
section.add(a[i]);
// Start recursion from the
// most significant pos position
return calculate(section, 30);
}
// Driver code
public static void main(String[] args)
{
int N = 4;
int A[] = { 3, 2, 5, 6 };
System.out.print(minXorValue(A, N));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation to find Minimum # possible value of the maximum xor # in an array by choosing some integer # Function to calculate Minimum possible # value of the Maximum XOR in an array def calculate(section, pos): # base case if (pos < 0): return 0 # Divide elements into two sections on_section = [] off_section = [] # Traverse all elements of current # section and divide in two groups for el in section: if (((el >> pos) & 1) == 0): off_section.append(el) else: on_section.append(el) # Check if one of the sections is empty if (len(off_section) == 0): return calculate(on_section, pos - 1) if (len(on_section) == 0): return calculate(off_section, pos - 1) # explore both the possibilities using recursion return min(calculate(off_section, pos - 1), calculate(on_section, pos - 1))+ (1 << pos) # Function to calculate minimum XOR value def minXorValue(a, n): section = [] for i in range( n): section.append(a[i]); # Start recursion from the # most significant pos position return calculate(section, 30) # Driver code if __name__ == "__main__": N = 4 A = [ 3, 2, 5, 6 ] print(minXorValue(A, N)) # This code is contributed by chitranayal
C#
// C# implementation to find minimum
// possible value of the maximum xor
// in an array by choosing some integer
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate minimum possible
// value of the maximum XOR in an array
static int calculate(List<int> section, int pos)
{
// Base case
if (pos < 0)
return 0;
// Divide elements into two sections
List<int> on_section = new List<int>(),
off_section = new List<int>();
// Traverse all elements of current
// section and divide in two groups
foreach(int el in section)
{
if (((el >> pos) & 1) == 0)
off_section.Add(el);
else
on_section.Add(el);
}
// Check if one of the sections is empty
if (off_section.Count == 0)
return calculate(on_section, pos - 1);
if (on_section.Count == 0)
return calculate(off_section, pos - 1);
// Explore both the possibilities using recursion
return Math.Min(calculate(off_section, pos - 1),
calculate(on_section, pos - 1)) +
(1 << pos);
}
// Function to calculate minimum XOR value
static int minXorValue(int []a, int n)
{
List<int> section = new List<int>();
for(int i = 0; i < n; i++)
section.Add(a[i]);
// Start recursion from the
// most significant pos position
return calculate(section, 30);
}
// Driver code
public static void Main(String[] args)
{
int N = 4;
int []A = { 3, 2, 5, 6 };
Console.Write(minXorValue(A, N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to find Minimum
// possible value of the maximum xor
// in an array by choosing some integer
// Function to calculate Minimum possible
// value of the Maximum XOR in an array
function calculate(section, pos)
{
// base case
if (pos < 0)
return 0;
// Divide elements into two sections
let on_section = [], off_section = [];
// Traverse all elements of current
// section and divide in two groups
for (let el = 0; el < section.length; el++) {
if (((section[el] >> pos) & 1) == 0)
off_section.push(section[el]);
else
on_section.push(section[el]);
}
// Check if one of the sections is empty
if (off_section.length == 0)
return calculate(on_section, pos - 1);
if (on_section.length == 0)
return calculate(off_section, pos - 1);
// explore both the possibilities using recursion
return Math.min(calculate(off_section, pos - 1),
calculate(on_section, pos - 1))
+ (1 << pos);
}
// Function to calculate minimum XOR value
function minXorValue(a, n)
{
let section = [];
for (let i = 0; i < n; i++)
section.push(a[i]);
// Start recursion from the
// most significant pos position
return calculate(section, 30);
}
// Driver code
let N = 4;
let A = [ 3, 2, 5, 6 ];
document.write(minXorValue(A, N));
</script>
Producción:
5
Complejidad de tiempo: O(N * log(max(A i ))