Dados N Nodes valorados por [1, N] , una array arr[] que consiste en N enteros positivos tales que el i -ésimo Node ( indexación basada en 1 ) tiene el valor arr[i] y un entero M , la tarea es encontrar el XOR bit a bit máximo de valores de Node de un gráfico acíclico formado por M aristas.
Ejemplos:
Entrada: arr[]= {1, 2, 3, 4}, M = 2
Salida: 7
Explicación:
Los gráficos acíclicos que tienen M(= 2) aristas pueden estar formados por vértices como:
- {1, 2, 3}: el valor de Bitwise XOR de los vértices es 1^2^3 = 0.
- {2, 3, 4}: el valor de Bitwise XOR de los vértices es 2^3^4 = 5.
- {1, 2, 4}: el valor de Bitwise XOR de los vértices es 1^2^4 = 7.
- {1, 4, 3}: el valor de Bitwise XOR de los vértices es 1^4^3 = 6.
Por lo tanto, el XOR bit a bit máximo entre todos los gráficos acíclicos posibles es 7.
Entrada: arr[] = {2, 4, 8, 16}, M = 2
Salida: 28
Enfoque: El problema dado se puede resolver utilizando el hecho de que un gráfico acíclico que tiene M aristas debe tener (M + 1) vértices . Por lo tanto, la tarea se reduce a encontrar el máximo Bitwise XOR de un subconjunto de la array arr[] que tiene (M + 1) vértices . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maxAns como 0 que almacena el XOR bit a bit máximo de un gráfico acíclico que tiene M bordes.
- Genere todos los subconjuntos posibles de la array arr[] y, para cada subconjunto, encuentre el Bitwise XOR de los elementos del subconjunto y actualice el valor de maxAns al máximo de maxAns y Bitwise XOR .
- Después de completar los pasos anteriores, imprima el valor de maxAns como resultado.
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 to find the maximum Bitwise
// XOR of any subset of the array of size K
int maximumXOR(int arr[], int n, int K)
{
// Number of node must K + 1 for
// K edges
K++;
// Stores the maximum Bitwise XOR
int maxXor = INT_MIN;
// Generate 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 the maximum Bitwise
// XOR obtained so far
maxXor = max(maxXor, cur_xor);
}
}
// Return the maximum XOR
return maxXor;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(int);
int M = 2;
cout << maximumXOR(arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the maximum Bitwise
// XOR of any subset of the array of size K
static int maximumXOR(int arr[], int n, int K)
{
// Number of node must K + 1 for
// K edges
K++;
// Stores the maximum Bitwise XOR
int maxXor = Integer.MIN_VALUE;
// Generate all subsets of the array
for(int i = 0; i < (1 << n); i++)
{
// Integer.bitCount() 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 the maximum Bitwise
// XOR obtained so far
maxXor = Math.max(maxXor, cur_xor);
}
}
// Return the maximum XOR
return maxXor;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4 };
int N = arr.length;
int M = 2;
System.out.println(maximumXOR(arr, N, M));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Function to find the maximum Bitwise
# XOR of any subset of the array of size K
def maximumXOR(arr, n, K):
# Number of node must K + 1 for
# K edges
K += 1
# Stores the maximum Bitwise XOR
maxXor = -10**9
# Generate all subsets of the array
for i in range(1<<n):
# __builtin_popcount() returns
# the number of sets bits in
# an integer
if (bin(i).count('1') == K):
# Initialize current xor as 0
cur_xor = 0
for j in range(n):
# 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 the maximum Bitwise
# XOR obtained so far
maxXor = max(maxXor, cur_xor)
# Return the maximum XOR
return maxXor
# Driver Code
if __name__ == '__main__':
arr= [1, 2, 3, 4 ]
N = len(arr)
M = 2
print (maximumXOR(arr, N, M))
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Linq;
class GFG{
// Function to find the maximum Bitwise
// XOR of any subset of the array of size K
static int maximumXOR(int []arr, int n, int K)
{
// Number of node must K + 1 for
// K edges
K++;
// Stores the maximum Bitwise XOR
int maxXor = Int32.MinValue;
// Generate all subsets of the array
for(int i = 0; i < (1 << n); i++)
{
// Finding number of sets
// bits in an integer
if (Convert.ToString(i, 2).Count(c => c == '1') == 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 the maximum Bitwise
// XOR obtained so far
maxXor = Math.Max(maxXor, cur_xor);
}
}
// Return the maximum XOR
return maxXor;
}
// Driver code
static void Main()
{
int [] arr = { 1, 2, 3, 4 };
int N = arr.Length;
int M = 2;
Console.WriteLine(maximumXOR(arr, N, M));
}
}
// This code is contributed by jana_sayantan.
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum Bitwise
// XOR of any subset of the array of size K
function maximumXOR(arr, n, K) {
// Number of node must K + 1 for
// K edges
K++;
// Stores the maximum Bitwise XOR
let maxXor = Number.MIN_SAFE_INTEGER;
// Generate all subsets of the array
for (let i = 0; i < (1 << n); i++) {
// __builtin_popcount() returns
// the number of sets bits in
// an integer
if ((i).toString(2).split('').
filter(x => x == '1').length == 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 the maximum Bitwise
// XOR obtained so far
maxXor = Math.max(maxXor, cur_xor);
}
}
// Return the maximum XOR
return maxXor;
}
// Driver Code
let arr = [1, 2, 3, 4];
let N = arr.length;
let M = 2;
document.write(maximumXOR(arr, N, M));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
7
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por tmprofessor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA