Dada una array arr[] de N enteros, donde N es un número par. La tarea es dividir los N enteros dados en dos subconjuntos iguales de modo que la suma de Bitwise XOR de todos los elementos de dos subconjuntos sea máxima.
Ejemplos:
Entrada: N= 4, arr[] = {1, 2, 3, 4}
Salida: 10
Explicación:
Hay 3 formas posibles: (1, 2)(3, 4) = (1^2)+(3^ 4) = 10 (1, 3)(2, 4) = (1^3)+(2^3) = 8 (1, 4)(2, 3) = (1^4)+(2^3) = 6 Por lo tanto, la suma máxima = 10Entrada: N= 6, arr[] = {4, 5, 3, 2, 5, 6}
Salida: 17
Enfoque ingenuo: la idea es verificar todas las distribuciones posibles de N/2 pares. Imprime el Bitwise XOR de la suma de todos los elementos de dos subconjuntos que es máximo.
Complejidad temporal: O(N*N!)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica mediante el enmascaramiento de bits . Siga los pasos a continuación para resolver el problema:
- Inicialmente, la máscara de bits es 0, si el bit está establecido, el par ya está seleccionado.
- Repita todos los pares posibles y verifique si es posible elegir un par, es decir, los bits de i y j no están configurados en la máscara :
- Si es posible tomar el par, busque la suma Bitwise XOR para el par actual y busque el siguiente par recursivamente.
- De lo contrario, verifique el siguiente par de elementos.
- Siga actualizando la suma máxima del par XOR en el paso anterior para cada llamada recursiva.
- Imprime el valor máximo de todos los pares posibles almacenados en dp[mask] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function that finds the maximum
// Bitwise XOR sum of the two subset
int xorSum(int a[], int n,
int mask, int dp[])
{
// Check if the current state is
// already computed
if (dp[mask] != -1)
{
return dp[mask];
}
// Initialize answer to minimum value
int max_value = 0;
// Iterate through all possible pairs
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// Check whether ith bit and
// jth bit of mask is not
// set then pick the pair
if (i != j &&
(mask & (1 << i)) == 0 &&
(mask & (1 << j)) == 0)
{
// For all possible pairs
// find maximum value pick
// current a[i], a[j] and
// set i, j th bits in mask
max_value = max(max_value, (a[i] ^ a[j]) +
xorSum(a, n, (mask | (1 << i) |
(1 << j)), dp));
}
}
}
// Store the maximum value
// and return the answer
return dp[mask] = max_value;
}
// Driver Code
int main()
{
int n = 4;
// Given array arr[]
int arr[] = { 1, 2, 3, 4 };
// Declare Initialize the dp states
int dp[(1 << n) + 5];
memset(dp, -1, sizeof(dp));
// Function Call
cout << (xorSum(arr, n, 0, dp));
}
// This code is contributed by Rohit_ranjan
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
public class GFG {
// Function that finds the maximum
// Bitwise XOR sum of the two subset
public static int xorSum(int a[], int n,
int mask, int[] dp)
{
// Check if the current state is
// already computed
if (dp[mask] != -1) {
return dp[mask];
}
// Initialize answer to minimum value
int max_value = 0;
// Iterate through all possible pairs
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Check whether ith bit and
// jth bit of mask is not
// set then pick the pair
if (i != j
&& (mask & (1 << i)) == 0
&& (mask & (1 << j)) == 0) {
// For all possible pairs
// find maximum value pick
// current a[i], a[j] and
// set i, j th bits in mask
max_value = Math.max(
max_value,
(a[i] ^ a[j])
+ xorSum(a, n,
(mask | (1 << i)
| (1 << j)),
dp));
}
}
}
// Store the maximum value
// and return the answer
return dp[mask] = max_value;
}
// Driver Code
public static void main(String args[])
{
int n = 4;
// Given array arr[]
int arr[] = { 1, 2, 3, 4 };
// Declare Initialize the dp states
int dp[] = new int[(1 << n) + 5];
Arrays.fill(dp, -1);
// Function Call
System.out.println(xorSum(arr, n, 0, dp));
}
}
Python3
# Python3 program to implement # the above approach # Function that finds the maximum # Bitwise XOR sum of the two subset def xorSum(a, n, mask, dp): # Check if the current state is # already computed if(dp[mask] != -1): return dp[mask] # Initialize answer to minimum value max_value = 0 # Iterate through all possible pairs for i in range(n): for j in range(i + 1, n): # Check whether ith bit and # jth bit of mask is not # set then pick the pair if(i != j and (mask & (1 << i)) == 0 and (mask & (1 << j)) == 0): # For all possible pairs # find maximum value pick # current a[i], a[j] and # set i, j th bits in mask max_value = max(max_value, (a[i] ^ a[j]) + xorSum(a, n, (mask | (1 << i) | (1 << j)), dp)) # Store the maximum value # and return the answer dp[mask] = max_value return dp[mask] # Driver Code n = 4 # Given array arr[] arr = [ 1, 2, 3, 4 ] # Declare Initialize the dp states dp = [-1] * ((1 << n) + 5) # Function call print(xorSum(arr, n, 0, dp)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function that finds the maximum
// Bitwise XOR sum of the two subset
public static int xorSum(int []a, int n,
int mask, int[] dp)
{
// Check if the current state is
// already computed
if (dp[mask] != -1)
{
return dp[mask];
}
// Initialize answer to minimum value
int max_value = 0;
// Iterate through all possible pairs
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Check whether ith bit and
// jth bit of mask is not
// set then pick the pair
if (i != j &&
(mask & (1 << i)) == 0 &&
(mask & (1 << j)) == 0)
{
// For all possible pairs
// find maximum value pick
// current a[i], a[j] and
// set i, j th bits in mask
max_value = Math.Max(
max_value,
(a[i] ^ a[j]) +
xorSum(a, n, (mask |
(1 << i) | (1 << j)), dp));
}
}
}
// Store the maximum value
// and return the answer
return dp[mask] = max_value;
}
// Driver Code
public static void Main(String []args)
{
int n = 4;
// Given array []arr
int []arr = { 1, 2, 3, 4 };
// Declare Initialize the dp states
int []dp = new int[(1 << n) + 5];
for(int i = 0; i < dp.Length; i++)
dp[i] = -1;
// Function call
Console.WriteLine(xorSum(arr, n, 0, dp));
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript program for the above approach
// Function that finds the maximum
// Bitwise XOR sum of the two subset
function xorSum(a, n, mask, dp)
{
// Check if the current state is
// already computed
if (dp[mask] != -1)
{
return dp[mask];
}
// Initialize answer to minimum value
var max_value = 0;
// Iterate through all possible pairs
for (var i = 0; i < n; i++)
{
for (var j = i + 1; j < n; j++)
{
// Check whether ith bit and
// jth bit of mask is not
// set then pick the pair
if (i != j &&
(mask & (1 << i)) == 0 &&
(mask & (1 << j)) == 0)
{
// For all possible pairs
// find maximum value pick
// current a[i], a[j] and
// set i, j th bits in mask
max_value = Math.max(max_value, (a[i] ^ a[j]) +
xorSum(a, n, (mask | (1 << i) |
(1 << j)), dp));
}
}
}
// Store the maximum value
// and return the answer
return dp[mask] = max_value;
}
// Driver Code
var n = 4;
// Given array arr[]
var arr = [1, 2, 3, 4];
// Declare Initialize the dp states
var dp = Array((1 << n) + 5).fill(-1);
// Function Call
document.write(xorSum(arr, n, 0, dp));
</script>
Producción:
10
Complejidad de tiempo: O(N 2 *2 N ), donde N es el tamaño de la array dada
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA