Dado un conjunto de enteros positivos. encuentre el valor máximo del subconjunto XOR en el conjunto dado. Complejidad del tiempo esperado O(n).
Ejemplos:
Input: set[] = {2, 4, 5}
Output: 7
The subset {2, 5} has maximum XOR value
Input: set[] = {9, 8, 5}
Output: 13
The subset {8, 5} has maximum XOR value
Input: set[] = {8, 1, 2, 12, 7, 6}
Output: 15
The subset {1, 2, 12} has maximum XOR value
Input: set[] = {4, 6}
Output: 6
The subset {6} has maximum XOR value
Tenga en cuenta que este problema es diferente del subarreglo máximo XOR . Aquí necesitamos encontrar un subconjunto en lugar de un subarreglo.
Una solución simple es generar todos los subconjuntos posibles de un conjunto dado, encontrar XOR de cada subconjunto y devolver el subconjunto con XOR máximo.
A continuación se muestra un algoritmo eficiente que funciona en tiempo O(n).
La idea se basa en los siguientes hechos:
- El número de bits para representar todos los elementos es fijo, que es de 32 bits para enteros en la mayoría de los compiladores.
- Si el elemento máximo tiene MSB de bit más significativo en la posición i, entonces el resultado es al menos 2 i
1. Initialize index of chosen elements as 0. Let this index be
'index'
2. Traverse through all bits starting from most significant bit.
Let i be the current bit.
......(a) Find the maximum element with i'th bit set. If there
is no element with i'th bit set, continue to smaller
bit.
......(b) Let the element with i'th bit set be maxEle and index
of this element be maxInd. Place maxEle at 'index' and
(by swapping set[index] and set[maxInd])
......(c) Do XOR of maxEle with all numbers having i'th bit as set.
......(d) Increment index
3. Return XOR of all elements in set[]. Note that set[] is modified
in step 2.c.
A continuación se muestra la implementación de este algoritmo.
C++
// C++ program to find
// maximum XOR subset
#include<bits/stdc++.h>
using namespace std;
// Number of bits to
// represent int
#define INT_BITS 32
// Function to return
// maximum XOR subset
// in set[]
int maxSubarrayXOR(int set[], int n)
{
// Initialize index of
// chosen elements
int index = 0;
// Traverse through all
// bits of integer
// starting from the most
// significant bit (MSB)
for (int i = INT_BITS-1; i >= 0; i--)
{
// Initialize index of
// maximum element and
// the maximum element
int maxInd = index;
int maxEle = INT_MIN;
for (int j = index; j < n; j++)
{
// If i'th bit of set[j]
// is set and set[j] is
// greater than max so far.
if ( (set[j] & (1 << i)) != 0
&& set[j] > maxEle )
maxEle = set[j], maxInd = j;
}
// If there was no
// element with i'th
// bit set, move to
// smaller i
if (maxEle == INT_MIN)
continue;
// Put maximum element
// with i'th bit set
// at index 'index'
swap(set[index], set[maxInd]);
// Update maxInd and
// increment index
maxInd = index;
// Do XOR of set[maxIndex]
// with all numbers having
// i'th bit as set.
for (int j=0; j<n; j++)
{
// XOR set[maxInd] those
// numbers which have the
// i'th bit set
if (j != maxInd &&
(set[j] & (1 << i)) != 0)
set[j] = set[j] ^ set[maxInd];
}
// Increment index of
// chosen elements
index++;
}
// Final result is
// XOR of all elements
int res = 0;
for (int i = 0; i < n; i++)
res ^= set[i];
return res;
}
// Driver program
int main()
{
int set[] = {9, 8, 5};
int n = sizeof(set) / sizeof(set[0]);
cout << "Max subset XOR is ";
cout << maxSubarrayXOR(set, n);
return 0;
}
Java
// Java program to find
// maximum XOR subset
import java.util.*;
class GFG {
// Number of bits to
// represent int
static final int INT_BITS = 32;
// Function to return
// maximum XOR subset
// in set[]
static int maxSubarrayXOR(int set[], int n)
{
// Initialize index of
// chosen elements
int index = 0;
// Traverse through all
// bits of integer
// starting from the most
// significant bit (MSB)
for (int i = INT_BITS - 1; i >= 0; i--)
{
// Initialize index of
// maximum element and
// the maximum element
int maxInd = index;
int maxEle = Integer.MIN_VALUE;
for (int j = index; j < n; j++) {
// If i'th bit of set[j]
// is set and set[j] is
// greater than max so far.
if ((set[j] & (1 << i)) != 0 && set[j] > maxEle)
{
maxEle = set[j];
maxInd = j;
}
}
// If there was no
// element with i'th
// bit set, move to
// smaller i
if (maxEle == -2147483648)
continue;
// Put maximum element
// with i'th bit set
// at index 'index'
int temp = set[index];
set[index] = set[maxInd];
set[maxInd] = temp;
// Update maxInd and
// increment index
maxInd = index;
// Do XOR of set[maxIndex]
// with all numbers having
// i'th bit as set.
for (int j = 0; j < n; j++) {
// XOR set[maxInd] those
// numbers which have the
// i'th bit set
if (j != maxInd && (set[j] & (1 << i)) != 0)
set[j] = set[j] ^ set[maxInd];
}
// Increment index of
// chosen elements
index++;
}
// Final result is
// XOR of all elements
int res = 0;
for (int i = 0; i < n; i++)
res ^= set[i];
return res;
}
// Driver code
public static void main(String arg[]) {
int set[] = {9, 8, 5};
int n = set.length;
System.out.print("Max subset XOR is ");
System.out.print(maxSubarrayXOR(set, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find
# maximum XOR subset
# Number of bits to
# represent int
INT_BITS=32
# Function to return
# maximum XOR subset
# in set[]
def maxSubarrayXOR(set,n):
# Initialize index of
# chosen elements
index = 0
# Traverse through all
# bits of integer
# starting from the most
# significant bit (MSB)
for i in range(INT_BITS-1,-1,-1):
# Initialize index of
# maximum element and
# the maximum element
maxInd = index
maxEle = -2147483648
for j in range(index,n):
# If i'th bit of set[j]
# is set and set[j] is
# greater than max so far.
if ( (set[j] & (1 << i)) != 0
and set[j] > maxEle ):
maxEle = set[j]
maxInd = j
# If there was no
# element with i'th
# bit set, move to
# smaller i
if (maxEle ==-2147483648):
continue
# Put maximum element
# with i'th bit set
# at index 'index'
temp=set[index]
set[index]=set[maxInd]
set[maxInd]=temp
# Update maxInd and
# increment index
maxInd = index
# Do XOR of set[maxIndex]
# with all numbers having
# i'th bit as set.
for j in range(n):
# XOR set[maxInd] those
# numbers which have the
# i'th bit set
if (j != maxInd and
(set[j] & (1 << i)) != 0):
set[j] = set[j] ^ set[maxInd]
# Increment index of
# chosen elements
index=index + 1
# Final result is
# XOR of all elements
res = 0
for i in range(n):
res =res ^ set[i]
return res
# Driver code
set= [9, 8, 5]
n =len(set)
print("Max subset XOR is ",end="")
print(maxSubarrayXOR(set, n))
# This code is contributed
# by Anant Agarwal.
C#
// C# program to find
// maximum XOR subset
using System;
class GFG
{
// Number of bits to
// represent int
static int INT_BITS = 32;
// Function to return
// maximum XOR subset
// in set[]
static int maxSubarrayXOR(int []set,
int n)
{
// Initialize index of
// chosen elements
int index = 0;
// Traverse through all
// bits of integer
// starting from the most
// significant bit (MSB)
for (int i = INT_BITS - 1;
i >= 0; i--)
{
// Initialize index of
// maximum element and
// the maximum element
int maxInd = index;
int maxEle = int.MinValue;
for (int j = index; j < n; j++)
{
// If i'th bit of set[j]
// is set and set[j] is
// greater than max so far.
if ((set[j] & (1 << i)) != 0 &&
set[j] > maxEle)
{
maxEle = set[j];
maxInd = j;
}
}
// If there was no
// element with i'th
// bit set, move to
// smaller i
if (maxEle == -2147483648)
continue;
// Put maximum element
// with i'th bit set
// at index 'index'
int temp = set[index];
set[index] = set[maxInd];
set[maxInd] = temp;
// Update maxInd and
// increment index
maxInd = index;
// Do XOR of set[maxIndex]
// with all numbers having
// i'th bit as set.
for (int j = 0; j < n; j++)
{
// XOR set[maxInd] those
// numbers which have the
// i'th bit set
if (j != maxInd && (set[j] &
(1 << i)) != 0)
set[j] = set[j] ^ set[maxInd];
}
// Increment index of
// chosen elements
index++;
}
// Final result is
// XOR of all elements
int res = 0;
for (int i = 0; i < n; i++)
res ^= set[i];
return res;
}
// Driver code
public static void Main()
{
int []set = {9, 8, 5};
int n = set.Length;
Console.Write("Max subset XOR is ");
Console.Write(maxSubarrayXOR(set, n));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to find maximum XOR subset
// Number of bits to represent int
$INT_BITS = 32;
// Function to return maximum XOR subset
// in set[]
function maxSubarrayXOR(&$set, $n)
{
global $INT_BITS;
// Initialize index of chosen elements
$index = 0;
// Traverse through all bits of integer
// starting from the most significant bit (MSB)
for ($i = $INT_BITS - 1; $i >= 0; $i--)
{
// Initialize index of maximum element
// and the maximum element
$maxInd = $index;
$maxEle = 0;
for ($j = $index; $j < $n; $j++)
{
// If i'th bit of set[j]
// is set and set[j] is
// greater than max so far.
if ( ($set[$j] & (1 << $i)) != 0 &&
$set[$j] > $maxEle )
{
$maxEle = $set[$j];
$maxInd = $j;
}
}
// If there was no element with i'th
// bit set, move to smaller i
if ($maxEle == 0)
continue;
// Put maximum element with i'th bit
// set at index 'index'
$t = $set[$index];
$set[$index] = $set[$maxInd];
$set[$maxInd] = $t;
// Update maxInd and increment index
$maxInd = $index;
// Do XOR of set[maxIndex] with all numbers
// having i'th bit as set.
for ($j = 0; $j < $n; $j++)
{
// XOR set[maxInd] those numbers which
// have the i'th bit set
if ($j != $maxInd &&
($set[$j] & (1 << $i)) != 0)
$set[$j] = $set[$j] ^ $set[$maxInd];
}
// Increment index of chosen elements
$index++;
}
// Final result is XOR of all elements
$res = 0;
for ($i = 0; $i < $n; $i++)
$res ^= $set[$i];
return $res;
}
// Driver Code
$set = array(9, 8, 5);
$n = sizeof($set);
echo "Max subset XOR is ";
echo maxSubarrayXOR($set, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to find
// maximum XOR subset
// Number of bits to
// represent int
let INT_BITS = 32;
// Function to return
// maximum XOR subset
// in set[]
function maxSubarrayXOR(set,n)
{
// Initialize index of
// chosen elements
let index = 0;
// Traverse through all
// bits of integer
// starting from the most
// significant bit (MSB)
for (let i = INT_BITS - 1; i >= 0; i--)
{
// Initialize index of
// maximum element and
// the maximum element
let maxInd = index;
let maxEle = Number.MIN_VALUE;
for (let j = index; j < n; j++) {
// If i'th bit of set[j]
// is set and set[j] is
// greater than max so far.
if ((set[j] & (1 << i)) != 0 && set[j] > maxEle)
{
maxEle = set[j];
maxInd = j;
}
}
// If there was no
// element with i'th
// bit set, move to
// smaller i
if (maxEle == Number.MIN_VALUE)
continue;
// Put maximum element
// with i'th bit set
// at index 'index'
let temp = set[index];
set[index] = set[maxInd];
set[maxInd] = temp;
// Update maxInd and
// increment index
maxInd = index;
// Do XOR of set[maxIndex]
// with all numbers having
// i'th bit as set.
for (let j = 0; j < n; j++) {
// XOR set[maxInd] those
// numbers which have the
// i'th bit set
if (j != maxInd && (set[j] & (1 << i)) != 0)
set[j] = set[j] ^ set[maxInd];
}
// Increment index of
// chosen elements
index++;
}
// Final result is
// XOR of all elements
let res = 0;
for (let i = 0; i < n; i++)
res ^= set[i];
return res;
}
// Driver code
let set=[9, 8, 5];
let n = set.length;
document.write("Max subset XOR is ");
document.write(maxSubarrayXOR(set, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Max subset XOR is 13
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Ilustración:
Let the input set be : {9, 8, 5}
We start from 31st bit [Assuming Integers are 32 bit
long]. The loop will continue without doing anything till 4'th bit.
The 4th bit is set in set[0] i.e. 9 and this is the maximum
element with 4th bit set. So we choose this element and check
if any other number has the same bit set. If yes, we XOR that
number with 9. The element set[1], i.e., 8 also has 4'th bit
set. Now set[] becomes {9, 1, 5}. We add 9 to the list of
chosen elements by incrementing 'index'
We move further and find the maximum number with 3rd bit set
which is set[2] i.e. 5 No other number in the array has 3rd
bit set. 5 is also added to the list of chosen element.
We then iterate for bit 2 (no number for this) and then for
1 which is 1. But numbers 9 and 5 have the 1st bit set. Thus
we XOR 9 and 5 with 1 and our set becomes (8, 1, 4)
Finally, we XOR current elements of set and get the result
as 8 ^ 1 ^ 4 = 13.
¿Como funciona esto?
Primero comprendamos un caso simple en el que todos los elementos tienen bits más significativos (MSB) en diferentes posiciones. La tarea en este caso particular es simple, necesitamos hacer XOR de todos los elementos.
Si la entrada contiene varios números con el mismo MSB, entonces no es obvio cuál de ellos deberíamos elegir para incluir en el XOR. Lo que hacemos es reducir la lista de entrada a una forma equivalente que no contenga más de un número de la misma longitud. Al tomar el elemento máximo, sabemos que el MSB de este estará allí en la salida. Deje que este MSB esté en la posición i. Si hay más elementos con el i-ésimo conjunto (o el mismo MSB), los aplicamos XOR con el número máximo para que el i-ésimo bit se convierta en 0 en ellos y el problema se reduzca a i-1 bits.
Referencias:
http://math.stackexchange.com/questions/48682/maximization-with-xor-operator
Nota: El método anterior es similar a la eliminación gaussiana. Considere una array de tamaño 32 xn donde 32 es el número de bits y n es el número de elementos en la array.
Este artículo es una contribución de Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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