Encuentre el xor máximo de k elementos en una array

Dada una array arr[] de N enteros y un entero K . La tarea es encontrar el subconjunto xor máximo de tamaño K de la array dada.
Ejemplos: 
 

Entrada: arr[] = {2, 5, 4, 1, 3, 7, 6, 8}, K = 3 
Salida: 15 
Obtenemos 15 seleccionando 4, 5, 6, 8
Entrada: arr[] = {3 , 4, 7, 7, 9}, K = 3 
Salida: 14 
 

Enfoque ingenuo: iterar sobre todos los subconjuntos de tamaño K de la array y encontrar el xor máximo entre ellos.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum xor for a
// subset of size k from the given array
int Max_Xor(int arr[], int n, int k)
{
 
    // Initialize result
    int maxXor = INT_MIN;
 
    // Traverse all subsets of the array
    for (int i = 0; i < (1 << n); i++) {
 
        // __builtin_popcount() returns the number
        // of sets bits in an integer
        if (__builtin_popcount(i) == k) {
 
            // Initialize current xor as 0
            int cur_xor = 0;
            for (int j = 0; j < n; j++) {
 
                // If jth bit is set in i then include
                // jth element in the current xor
                if (i & (1 << j))
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update maximum xor so far
            maxXor = max(maxXor, cur_xor);
        }
    }
    return maxXor;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int n = sizeof(arr) / sizeof(int);
    int k = 3;
 
    cout << Max_Xor(arr, n, k);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the maximum xor for a
// subset of size k from the given array
static int Max_Xor(int arr[], int n, int k)
{
 
    // Initialize result
    int maxXor = Integer.MIN_VALUE;
 
    // Traverse all subsets of the array
    for (int i = 0; i < (1 << n); i++)
    {
 
        // __builtin_popcount() returns the number
        // of sets bits in an integer
        if (Integer.bitCount(i) == k)
        {
 
            // Initialize current xor as 0
            int cur_xor = 0;
            for (int j = 0; j < n; j++)
            {
 
                // If jth bit is set in i then include
                // jth element in the current xor
                if ((i & (1 << j)) == 0)
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update maximum xor so far
            maxXor = Math.max(maxXor, cur_xor);
        }
    }
    return maxXor;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int n = arr.length;
    int k = 3;
 
    System.out.println(Max_Xor(arr, n, k));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python implementation of the approach
 
MAX = 10000
MAX_ELEMENT = 50
 
dp =[[[-1 for i in range(MAX)]
    for j in range(MAX_ELEMENT)]
    for k in range(MAX_ELEMENT)]
 
# Function to return the maximum xor for a
# subset of size j from the given array
def Max_Xor(arr, i, j, mask, n):
    if (i >= n):
         
        # If the subset is complete then return
        # the xor value of the selected elements
        if (j == 0):
            return mask
        else:
            return 0
     
    # Return if already calculated for some
    # mask and j at the i'th index
    if (dp[i][j][mask] != -1):
        return dp[i][j][mask]
     
    # Initialize answer to 0
    ans = 0
     
    # If we can still include elements in our subset
    # include the i'th element
    if (j > 0):
        ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n)
         
    # Exclude the i'th element
    # ans store the max of both operations
    ans = max(ans, Max_Xor(arr, i + 1, j, mask, n))
    dp[i][j][mask] = ans
    return ans
 
# Driver code
arr = [2, 5, 4, 1, 3, 7, 6, 8]
n = len(arr)
k = 3
 
print(Max_Xor(arr, 0, k, 0, n))
 
# This code is contributed by shubhamsingh10

C#

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to return the maximum xor for a
// subset of size k from the given array
static int Max_Xor(int []arr, int n, int k)
{
 
    // Initialize result
    int maxXor = int.MinValue;
 
    // Traverse all subsets of the array
    for (int i = 0; i < (1 << n); i++)
    {
 
        // __builtin_popcount() returns the number
        // of sets bits in an integer
        if (bitCount(i) == k)
        {
 
            // Initialize current xor as 0
            int cur_xor = 0;
            for (int j = 0; j < n; j++)
            {
 
                // If jth bit is set in i then include
                // jth element in the current xor
                if ((i & (1 << j)) == 0)
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update maximum xor so far
            maxXor = Math.Max(maxXor, cur_xor);
        }
    }
    return maxXor;
}
 
static int bitCount(long x)
{
    int setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
    return setBits;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int n = arr.Length;
    int k = 3;
 
    Console.WriteLine(Max_Xor(arr, n, k));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximum xor for a
// subset of size k from the given array
function Max_Xor(arr, n, k)
{
 
    // Initialize result
    let maxXor = Number.MIN_VALUE;
 
    // Traverse all subsets of the array
    for (let i = 0; i < (1 << n); i++) {
 
        // bitCount() returns the number
        // of sets bits in an integer
        if (bitCount(i) == k) {
 
            // Initialize current xor as 0
            let cur_xor = 0;
            for (let j = 0; j < n; j++) {
 
                // If jth bit is set in i then include
                // jth element in the current xor
                if (i & (1 << j))
                    cur_xor = cur_xor ^ arr[j];
            }
 
            // Update maximum xor so far
            maxXor = Math.max(maxXor, cur_xor);
        }
    }
    return maxXor;
}
 
function bitCount(x)
{
    let setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
    return setBits;
}
 
// Driver code
    let arr = [ 2, 5, 4, 1, 3, 7, 6, 8 ];
    let n = arr.length;
    let k = 3;
 
    document.write(Max_Xor(arr, n, k));
 
</script>
Producción: 

15

 

Complejidad del tiempo: O(n*2 n )

Espacio Auxiliar: O(1)

Enfoque eficiente: el problema se puede resolver mediante programación dinámica . Cree una tabla dp dp[i][j][máscara] que almacene el xor máximo posible en el i -ésimo índice (con o sin incluirlo) y j indica el número de elementos restantes que podemos incluir en nuestro subconjunto de K elementos. Máscara es el xor de todos los elementos seleccionados hasta el i -ésimo índice. 
Nota: este enfoque solo funcionará para arreglos más pequeños debido a los requisitos de espacio para el arreglo dp.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 10000
#define MAX_ELEMENT 50
 
int dp[MAX_ELEMENT][MAX_ELEMENT][MAX];
 
// Function to return the maximum xor for a
// subset of size j from the given array
int Max_Xor(int arr[], int i, int j, int mask, int n)
{
    if (i >= n) {
 
        // If the subset is complete then return
        // the xor value of the selected elements
        if (j == 0)
            return mask;
        else
            return 0;
    }
 
    // Return if already calculated for some
    // mask and j at the i'th index
    if (dp[i][j][mask] != -1)
        return dp[i][j][mask];
 
    // Initialize answer to 0
    int ans = 0;
 
    // If we can still include elements in our subset
    // include the i'th element
    if (j > 0)
        ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n);
 
    // Exclude the i'th element
    // ans store the max of both operations
    ans = max(ans, Max_Xor(arr, i + 1, j, mask, n));
 
    return dp[i][j][mask] = ans;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int n = sizeof(arr) / sizeof(int);
    int k = 3;
 
    memset(dp, -1, sizeof(dp));
 
    cout << Max_Xor(arr, 0, k, 0, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static int MAX = 10000;
static int MAX_ELEMENT = 50;
 
static int [][][] dp = new int[MAX_ELEMENT][MAX_ELEMENT][MAX];
 
// Function to return the maximum xor for a
// subset of size j from the given array
static int Max_Xor(int arr[], int i,
                   int j, int mask, int n)
{
    if (i >= n)
    {
 
        // If the subset is complete then return
        // the xor value of the selected elements
        if (j == 0)
            return mask;
        else
            return 0;
    }
 
    // Return if already calculated for some
    // mask and j at the i'th index
    if (dp[i][j][mask] != -1)
        return dp[i][j][mask];
 
    // Initialize answer to 0
    int ans = 0;
 
    // If we can still include elements in our subset
    // include the i'th element
    if (j > 0)
        ans = Max_Xor(arr, i + 1, j - 1,
                      mask ^ arr[i], n);
 
    // Exclude the i'th element
    // ans store the max of both operations
    ans = Math.max(ans, Max_Xor(arr, i + 1, j,
                                mask, n));
 
    return dp[i][j][mask] = ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int n = arr.length;
    int k = 3;
 
    for(int i = 0; i < MAX_ELEMENT; i++)
    {
        for(int j = 0; j < MAX_ELEMENT; j++)
        {
            for(int l = 0; l < MAX; l++)
            dp[i][j][l] = -1;
        }
    }
 
    System.out.println(Max_Xor(arr, 0, k, 0, n));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python implementation of the approach
 
MAX = 10000
MAX_ELEMENT = 50
 
dp =[[[-1 for i in range(MAX)] for j in range(MAX_ELEMENT)] for k in range(MAX_ELEMENT)]
 
# Function to return the maximum xor for a
# subset of size j from the given array
def Max_Xor(arr, i, j, mask, n):
    if (i >= n):
         
        # If the subset is complete then return
        # the xor value of the selected elements
        if (j == 0):
            return mask
        else:
            return 0
     
    # Return if already calculated for some
    # mask and j at the i'th index
    if (dp[i][j][mask] != -1):
        return dp[i][j][mask]
     
    # Initialize answer to 0
    ans = 0
     
    # If we can still include elements in our subset
    # include the i'th element
    if (j > 0):
        ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n)
         
    # Exclude the i'th element
    # ans store the max of both operations
    ans = max(ans, Max_Xor(arr, i + 1, j, mask, n))
    dp[i][j][mask] = ans
    return ans
 
 
# Driver code
 
arr = [2, 5, 4, 1, 3, 7, 6, 8]
n = len(arr)
k = 3
 
print(Max_Xor(arr, 0, k, 0, n))
 
# This code is contributed by shubhamsingh10

C#

// C# implementation of the approach
using System;
 
class GFG
{
  static int MAX = 10000;
  static int MAX_ELEMENT = 50;
  static int [,,] dp = new int[MAX_ELEMENT, MAX_ELEMENT, MAX];
 
  // Function to return the maximum xor for a
  // subset of size j from the given array
  static int Max_Xor(int[] arr, int i,
                     int j, int mask, int n)
  {
    if (i >= n)
    {
 
      // If the subset is complete then return
      // the xor value of the selected elements
      if (j == 0)
        return mask;
      else
        return 0;
    }
 
    // Return if already calculated for some
    // mask and j at the i'th index
    if (dp[i,j,mask] != -1)
      return dp[i,j,mask];
 
    // Initialize answer to 0
    int ans = 0;
 
    // If we can still include elements in our subset
    // include the i'th element
    if (j > 0)
      ans = Max_Xor(arr, i + 1, j - 1,
                    mask ^ arr[i], n);
 
    // Exclude the i'th element
    // ans store the max of both operations
    ans = Math.Max(ans, Max_Xor(arr, i + 1, j,
                                mask, n));
 
    return dp[i,j,mask] = ans;
  }
 
  // Driver code
  public static void Main ()
  {
    int[] arr = { 2, 5, 4, 1, 3, 7, 6, 8 };
    int n = arr.Length;
    int k = 3;
 
    for(int i = 0; i < MAX_ELEMENT; i++)
    {
      for(int j = 0; j < MAX_ELEMENT; j++)
      {
        for(int l = 0; l < MAX; l++)
          dp[i,j,l] = -1;
      }
    }
 
    Console.WriteLine(Max_Xor(arr, 0, k, 0, n));
  }
}
 
// This code is contributed by target_2.

Javascript

//JS implementation of the approach
 
const MAX = 10000;
const MAX_ELEMENT = 50;
 
//declaring and building dp
var dp = [];
for (var i = 0; i < MAX_ELEMENT; i++)
{
    dp[i] = [];
    for (var j = 0; j < MAX_ELEMENT; j++)
    {
        dp[i][j] = [];
        for (var k = 0; k < MAX_ELEMENT; k++)
        {
            dp[i][j][k] = -1;
        }
    }
}
 
 
 
// Function to return the maximum xor for a
// subset of size j from the given array
function Max_Xor(arr, i, j, mask, n)
{
    if (i >= n)
    {
        // If the subset is complete then return
        // the xor value of the selected elements
        if (j == 0)
            return mask;
        else
            return 0;
    }
     
    // Return if already calculated for some
    // mask and j at the i'th index
    if (dp[i][j][mask] != -1)
        return dp[i][j][mask];
     
    // Initialize answer to 0
    var ans = 0;
     
    // If we can still include elements in our subset
    // include the i'th element
    if (j > 0)
        ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n);
         
    // Exclude the i'th element
    // ans store the max of both operations
    ans = Math.max(ans, Max_Xor(arr, i + 1, j, mask, n));
    dp[i][j][mask] = ans;
    return ans;
}
 
 
// Driver code
 
var arr = [2, 5, 4, 1, 3, 7, 6, 8];
var n = arr.length;
var k = 3;
 
console.log(Max_Xor(arr, 0, k, 0, n));
 
// This code is contributed by phasing17
Producción: 

15

 

Complejidad temporal: O(n*n)

Espacio auxiliar: O(MAX*MAX_ELEMENT 2 ) donde MAX y MAX_ELEMENT son constantes definidas.

Publicación traducida automáticamente

Artículo escrito por syntaxerror 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 *