Dada una array de enteros no negativos. Elija un entero P y tome XOR de P con todos los elementos de la array. La tarea es elegir P tal que el valor máximo de la array sea el mínimo posible después de realizar XOR de todos los elementos de la array con P.
Ejemplos:
Entrada: arr = {3, 2, 1}
Salida: 2
Explicación:
Podemos elegir P = 3 de modo que después de tomar XOR el elemento máximo sea el mínimo posible.
Después de tomar OR exclusivo arr = {0, 1, 2}
2 es el valor mínimo posible.
Entrada: arr = {5, 1}
Salida: 4
Acercarse:
- Podemos resolver este problema recursivamente a partir del bit más significativo.
- Divida los elementos en dos grupos, uno con los elementos que tienen el bit actual activado (1) y otro con los elementos que tienen el bit actual desactivado (0).
- Si alguno de los grupos está vacío, podemos asignar el bit actual de P en consecuencia para que tengamos el bit actual desactivado en nuestra respuesta.
- De lo contrario, si ambos grupos no están vacíos, sea cual sea el valor que asignemos al bit actual de P, tendremos este bit en (1) en nuestra respuesta.
- Ahora, para decidir qué valor asignar al bit actual de P, llamaremos recursivamente a cada uno de los grupos para el siguiente bit y devolveremos el mínimo de ambos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program that find the minimum
// possible maximum
#include <bits/stdc++.h>
using namespace std;
// Recursive function that find the
// minimum value after exclusive-OR
int RecursiveFunction(vector<int> ref,
int bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (ref.size() == 0 || bit < 0)
return 0;
vector<int> curr_on, curr_off;
for (int i = 0; i < ref.size(); i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((ref[i] >> bit) & 1) == 0)
curr_off.push_back(ref[i]);
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.push_back(ref[i]);
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.size() == 0)
return RecursiveFunction(curr_on,
bit - 1);
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.size() == 0)
return RecursiveFunction(curr_off,
bit - 1);
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return min(RecursiveFunction(curr_off,
bit - 1),
RecursiveFunction(curr_on,
bit - 1))
+ (1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
void PrintMinimum(int a[], int n)
{
vector<int> v;
// Pushing values in vector
for (int i = 0; i < n; i++)
v.push_back(a[i]);
// Printing answer
cout << RecursiveFunction(v, 30)
<< "\n";
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
PrintMinimum(arr, size);
return 0;
}
Java
// Java program that find the minimum
// possible maximum
import java.util.*;
class GFG{
// Recursive function that find the
// minimum value after exclusive-OR
static int RecursiveFunction(ArrayList<Integer> ref,
int bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (ref.size() == 0 || bit < 0)
return 0;
ArrayList<Integer> curr_on = new ArrayList<>();
ArrayList<Integer> curr_off = new ArrayList<>();
for(int i = 0; i < ref.size(); i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((ref.get(i) >> bit) & 1) == 0)
curr_off.add(ref.get(i));
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.add(ref.get(i));
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.size() == 0)
return RecursiveFunction(curr_on, bit - 1);
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.size() == 0)
return RecursiveFunction(curr_off, bit - 1);
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return Math.min(RecursiveFunction(curr_off,
bit - 1),
RecursiveFunction(curr_on,
bit - 1)) +
(1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
static void PrintMinimum(int a[], int n)
{
ArrayList<Integer> v = new ArrayList<>();
// Pushing values in vector
for(int i = 0; i < n; i++)
v.add(a[i]);
// Printing answer
System.out.println(RecursiveFunction(v, 30));
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 1 };
int size = arr.length;
PrintMinimum(arr, size);
}
}
// This code is contributed by jrishabh99
Python3
# Python3 program that find # the minimum possible maximum # Recursive function that find the # minimum value after exclusive-OR def RecursiveFunction(ref, bit): # Condition if ref size is zero or # bit is negative then return 0 if(len(ref) == 0 or bit < 0): return 0; curr_on = [] curr_off = [] for i in range(len(ref)): # Condition if current bit is # off then push current value # in curr_off vector if(((ref[i] >> bit) & 1) == 0): curr_off.append(ref[i]) # Condition if current bit is on # then push current value in # curr_on vector else: curr_on.append(ref[i]) # Condition if curr_off is empty # then call recursive function # on curr_on vector if(len(curr_off) == 0): return RecursiveFunction(curr_on, bit - 1) # Condition if curr_on is empty # then call recursive function # on curr_off vector if(len(curr_on) == 0): return RecursiveFunction(curr_off, bit - 1) # Return the minimum of curr_off and # curr_on and add power of 2 of # current bit return(min(RecursiveFunction(curr_off, bit - 1), RecursiveFunction(curr_on, bit - 1)) + (1 << bit)) # Function that print the minimum # value after exclusive-OR def PrintMinimum(a, n): v = [] # Pushing values in vector for i in range(n): v.append(a[i]) # Printing answer print(RecursiveFunction(v, 30)) # Driver Code arr = [3, 2, 1] size = len(arr) PrintMinimum(arr, size) #This code is contributed by avanitrachhadiya2155
C#
// C# program that find the minimum
// possible maximum
using System;
using System.Collections.Generic;
class GFG{
// Recursive function that find the
// minimum value after exclusive-OR
static int RecursiveFunction(List<int> re,
int bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (re.Count == 0 || bit < 0)
return 0;
List<int> curr_on = new List<int>();
List<int> curr_off = new List<int>();
for(int i = 0; i < re.Count; i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((re[i] >> bit) & 1) == 0)
curr_off.Add(re[i]);
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.Add(re[i]);
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.Count == 0)
return RecursiveFunction(curr_on,
bit - 1);
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.Count == 0)
return RecursiveFunction(curr_off,
bit - 1);
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return Math.Min(RecursiveFunction(curr_off,
bit - 1),
RecursiveFunction(curr_on,
bit - 1)) +
(1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
static void PrintMinimum(int []a, int n)
{
List<int> v = new List<int>();
// Pushing values in vector
for(int i = 0; i < n; i++)
v.Add(a[i]);
// Printing answer
Console.WriteLine(RecursiveFunction(v, 30));
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 2, 1 };
int size = arr.Length;
PrintMinimum(arr, size);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program that find the minimum
// possible maximum
// Recursive function that find the
// minimum value after exclusive-OR
function RecursiveFunction(ref, bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (ref.length == 0 || bit < 0)
return 0;
let curr_on = [], curr_off = [];
for (let i = 0; i < ref.length; i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((ref[i] >> bit) & 1) == 0)
curr_off.push(ref[i]);
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.push(ref[i]);
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.length == 0)
return RecursiveFunction(curr_on,
bit - 1);
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.length == 0)
return RecursiveFunction(curr_off,
bit - 1);
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return Math.min(RecursiveFunction(curr_off,
bit - 1),
RecursiveFunction(curr_on,
bit - 1))
+ (1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
function PrintMinimum(a, n)
{
let v = [];
// Pushing values in vector
for (let i = 0; i < n; i++)
v.push(a[i]);
// Printing answer
document.write(RecursiveFunction(v, 30)
+ "<br>");
}
// Driver Code
let arr = [ 3, 2, 1 ];
let size = arr.length;
PrintMinimum(arr, size);
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA