Dada una array arr[] que consta de N enteros, la tarea es encontrar el tamaño del conjunto S tal que Bitwise XOR de cualquier subconjunto de la array arr[] exista en el conjunto S.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 8
Explicación:
Todos los valores XOR bit a bit posibles de los subconjuntos de la array arr[] son {0, 1, 2, 3, 4, 5, 6 , 7}.
Por lo tanto, el tamaño del conjunto requerido es 8.Entrada: arr[] = {6}
Salida: 1
Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos no vacíos posibles de la array dada arr[] y almacenar el XOR bit a bit de todos los subconjuntos en un conjunto . Después de generar todos los subconjuntos, imprima el tamaño del conjunto obtenido 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;
// Stores the Bitwise XOR
// of every possible subset
unordered_set<int> s;
// Function to generate all
// combinations of subsets and
// store their Bitwise XOR in set S
void countXOR(int arr[], int comb[],
int start, int end,
int index, int r)
{
// If the end of the
// subset is reached
if (index == r) {
// Stores the Bitwise XOR
// of the current subset
int new_xor = 0;
// Iterate comb[] to find XOR
for (int j = 0; j < r; j++) {
new_xor ^= comb[j];
}
// Insert the Bitwise
// XOR of R elements
s.insert(new_xor);
return;
}
// Otherwise, iterate to
// generate all possible subsets
for (int i = start;
i <= end && end - i + 1 >= r - index; i++) {
comb[index] = arr[i];
// Recursive call for next index
countXOR(arr, comb, i + 1, end,
index + 1, r);
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subsets of the given array
void maxSizeSet(int arr[], int N)
{
// Iterate over the given array
for (int r = 2; r <= N; r++) {
int comb[r + 1];
// Generate all possible subsets
countXOR(arr, comb, 0, N - 1,
0, r);
}
// Print the size of the set
cout << s.size() << endl;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
maxSizeSet(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Stores the Bitwise XOR
// of every possible subset
static HashSet<Integer> s;
// Function to generate all
// combinations of subsets and
// store their Bitwise XOR in set S
static void countXOR(int arr[], int comb[],
int start, int end,
int index, int r)
{
// If the end of the
// subset is reached
if (index == r)
{
// Stores the Bitwise XOR
// of the current subset
int new_xor = 0;
// Iterate comb[] to find XOR
for(int j = 0; j < r; j++)
{
new_xor ^= comb[j];
}
// Insert the Bitwise
// XOR of R elements
s.add(new_xor);
return;
}
// Otherwise, iterate to
// generate all possible subsets
for(int i = start;
i <= end && end - i + 1 >= r - index;
i++)
{
comb[index] = arr[i];
// Recursive call for next index
countXOR(arr, comb, i + 1, end, index + 1, r);
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subsets of the given array
static void maxSizeSet(int arr[], int N)
{
// Iterate over the given array
for(int r = 1; r <= N; r++)
{
int comb[] = new int[r + 1];
// Generate all possible subsets
countXOR(arr, comb, 0, N - 1, 0, r);
}
// Print the size of the set
System.out.println(s.size());
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = arr.length;
// Initialize set
s = new HashSet<>();
// Function Call
maxSizeSet(arr, N);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Stores the Bitwise XOR # of every possible subset s = set([]) # Function to generate all # combinations of subsets and # store their Bitwise XOR in set S def countXOR(arr, comb, start, end, index, r): # If the end of the # subset is reached if (index == r) : # Stores the Bitwise XOR # of the current subset new_xor = 0 # Iterate comb[] to find XOR for j in range(r): new_xor ^= comb[j] # Insert the Bitwise # XOR of R elements s.add(new_xor) return # Otherwise, iterate to # generate all possible subsets i = start while i <= end and (end - i + 1) >= (r - index): comb[index] = arr[i] # Recursive call for next index countXOR(arr, comb, i + 1, end, index + 1, r) i += 1 # Function to find the size of the # set having Bitwise XOR of all the # subsets of the given array def maxSizeSet(arr, N): # Iterate over the given array for r in range(2, N + 1): comb = [0]*(r + 1) # Generate all possible subsets countXOR(arr, comb, 0, N - 1, 0, r) # Print the size of the set print(len(s)) arr = [ 1, 2, 3, 4, 5 ] N = len(arr) # Function Call maxSizeSet(arr, N) # This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Stores the Bitwise XOR
// of every possible subset
static HashSet<int> s;
// Function to generate all
// combinations of subsets and
// store their Bitwise XOR in set S
static void countXOR(int []arr, int []comb,
int start, int end,
int index, int r)
{
// If the end of the
// subset is reached
if (index == r)
{
// Stores the Bitwise XOR
// of the current subset
int new_xor = 0;
// Iterate comb[] to find XOR
for(int j = 0; j < r; j++)
{
new_xor ^= comb[j];
}
// Insert the Bitwise
// XOR of R elements
s.Add(new_xor);
return;
}
// Otherwise, iterate to
// generate all possible subsets
for(int i = start;
i <= end && end - i + 1 >= r - index;
i++)
{
comb[index] = arr[i];
// Recursive call for next index
countXOR(arr, comb, i + 1, end, index + 1, r);
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subsets of the given array
static void maxSizeSet(int []arr, int N)
{
// Iterate over the given array
for(int r = 1; r <= N; r++)
{
int []comb = new int[r + 1];
// Generate all possible subsets
countXOR(arr, comb, 0, N - 1, 0, r);
}
// Print the size of the set
Console.WriteLine(s.Count);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5 };
int N = arr.Length;
// Initialize set
s = new HashSet<int>();
// Function Call
maxSizeSet(arr, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Stores the Bitwise XOR
// of every possible subset
let s;
// Function to generate all
// combinations of subsets and
// store their Bitwise XOR in set S
function countXOR(arr,comb,start,end,index,r)
{
// If the end of the
// subset is reached
if (index == r)
{
// Stores the Bitwise XOR
// of the current subset
let new_xor = 0;
// Iterate comb[] to find XOR
for(let j = 0; j < r; j++)
{
new_xor ^= comb[j];
}
// Insert the Bitwise
// XOR of R elements
s.add(new_xor);
return;
}
// Otherwise, iterate to
// generate all possible subsets
for(let i = start;
i <= end && end - i + 1 >= r - index;
i++)
{
comb[index] = arr[i];
// Recursive call for next index
countXOR(arr, comb, i + 1, end, index + 1, r);
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subsets of the given array
function maxSizeSet(arr,N)
{
// Iterate over the given array
for(let r = 1; r <= N; r++)
{
let comb = new Array(r + 1);
// Generate all possible subsets
countXOR(arr, comb, 0, N - 1, 0, r);
}
// Print the size of the set
document.write(s.size);
}
// Driver Code
let arr=[1, 2, 3, 4, 5 ];
let N = arr.length;
// Initialize set
s = new Set();
// Function Call
maxSizeSet(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
8
Complejidad temporal: O(N N )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el enfoque codicioso y la eliminación gaussiana . Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar, digamos dp[] de tamaño 20, que almacene la máscara de cada elemento de la array y la inicialice con 0 .
- Inicialice una variable, digamos ans como 0 , para almacenar el tamaño de la array dp[] .
- Recorra la array dada arr[] y para cada elemento de la array arr[], realice los siguientes pasos:
- Inicialice una variable, digamos mask as arr[i] , para verificar la posición del bit establecido más significativo.
- Si se establece el i -ésimo bit desde la derecha de arr[i] y dp[i] es 0 , entonces actualice la array dp[i] como 2 i e incremente el valor de ans en 1 y salga del bucle .
- De lo contrario, actualice el valor de la máscara como Bitwise XOR de la máscara y dp[i] .
- Después de completar los pasos anteriores, imprima el valor de 2 ans como el tamaño resultante del conjunto de elementos requerido.
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;
int const size = 20;
// Stores the mask of the vector
int dp[size];
// Stores the current size of dp[]
int ans;
// Function to store the
// mask of given integer
void insertVector(int mask)
{
// Iterate over the range [0, 20]
for (int i = 0; i < 20; i++) {
// If i-th bit 0
if ((mask & 1 << i) == 0)
continue;
// If dp[i] is zero
if (!dp[i]) {
// Store the position in dp
dp[i] = mask;
// Increment the answer
++ans;
// Return from the loop
return;
}
// mask = mask XOR dp[i]
mask ^= dp[i];
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subset of the given array
void maxSizeSet(int arr[], int N)
{
// Traverse the array
for (int i = 0; i < N; i++) {
insertVector(arr[i]);
}
// Print the answer
cout << (1 << ans) << endl;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
maxSizeSet(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
final static int size = 20;
// Stores the mask of the vector
static int[] dp = new int[size];
// Stores the current size of dp[]
static int ans;
// Function to store the
// mask of given integer
static void insertVector(int mask)
{
// Iterate over the range [0, 20]
for (int i = 0; i < 20; i++) {
// If i-th bit 0
if ((mask & 1 << i) == 0)
continue;
// If dp[i] is zero
if (dp[i]==0) {
// Store the position in dp
dp[i] = mask;
// Increment the answer
++ans;
// Return from the loop
return;
}
// mask = mask XOR dp[i]
mask ^= dp[i];
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subset of the given array
static void maxSizeSet(int[] arr, int N)
{
// Traverse the array
for (int i = 0; i < N; i++) {
insertVector(arr[i]);
}
// Print the answer
System.out.println(1<<ans);
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 5 };
int N = arr.length;
// Function Call
maxSizeSet(arr, N);
}
}
//This code is contributed by Hritik Dwivedi
Python3
# Python3 program for the above approach # Stores the mask of the vector dp = [0]*20 # Stores the current 20 of dp[] ans = 0 # Function to store the # mask of given integer def insertVector(mask): global dp, ans # Iterate over the range [0, 20] for i in range(20): # If i-th bit 0 if ((mask & 1 << i) == 0): continue # If dp[i] is zero if (not dp[i]): # Store the position in dp dp[i] = mask # Increment the answer ans += 1 # Return from the loop return # mask = mask XOR dp[i] mask ^= dp[i] # Function to find the 20 of the # set having Bitwise XOR of all the # subset of the given array def maxSizeSet(arr, N): # Traverse the array for i in range(N): insertVector(arr[i]) # Print the answer print ((1 << ans)) # Driver Code if __name__ == '__main__': arr = [1, 2, 3, 4, 5] N = len(arr) # Function Call maxSizeSet(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG{
static int size = 20;
// Stores the mask of the vector
static int[] dp = new int[size];
// Stores the current size of dp[]
static int ans;
// Function to store the
// mask of given integer
static void insertVector(int mask)
{
// Iterate over the range [0, 20]
for(int i = 0; i < 20; i++)
{
// If i-th bit 0
if ((mask & 1 << i) == 0)
continue;
// If dp[i] is zero
if (dp[i] == 0)
{
// Store the position in dp
dp[i] = mask;
// Increment the answer
++ans;
// Return from the loop
return;
}
// mask = mask XOR dp[i]
mask ^= dp[i];
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subset of the given array
static void maxSizeSet(int[] arr, int N)
{
// Traverse the array
for(int i = 0; i < N; i++)
{
insertVector(arr[i]);
}
// Print the answer
Console.WriteLine(1 << ans);
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5 };
int N = arr.Length;
// Function Call
maxSizeSet(arr, N);
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
let size = 20;
// Stores the mask of the vector
var dp = new Array(size).fill(0);
// Stores the current size of dp[]
let ans = 0;
// Function to store the
// mask of given integer
function insertVector(mask)
{
// Iterate over the range [0, 20]
for(let i = 0; i < 20; i++)
{
// If i-th bit 0
if ((mask & 1 << i) == 0)
continue;
// If dp[i] is zero
if (dp[i] == 0)
{
// Store the position in dp
dp[i] = mask;
// Increment the answer
++ans;
// Return from the loop
return;
}
// mask = mask XOR dp[i]
mask ^= dp[i];
}
}
// Function to find the size of the
// set having Bitwise XOR of all the
// subset of the given array
function maxSizeSet(arr, N)
{
// Traverse the array
for(let i = 0; i < N; i++)
{
insertVector(arr[i]);
}
// Print the answer
document.write(1<<ans);
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5 ];
let N = arr.length;
// Function Call
maxSizeSet(arr, N);
// This code is contributed by nitin_sharma
</script>
Producción:
8
Complejidad de Tiempo: O(M * N)
Espacio Auxiliar: O(M * N)