Given an array arr[] consisting of N integers, the task is to find the size of the set S such that Bitwise XOR of any subset of the array arr[] exists in the set S.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 8
Explanation:
All possible Bitwise XOR values of subsets of the array arr[] are {0, 1, 2, 3, 4, 5, 6, 7}.
Therefore, the size of the required set is 8.Input: arr[] = {6}
Output: 1
Naive Approach: The simplest approach is to generate all possible non-empty subsets of the given array arr[] and store the Bitwise XOR of all subsets in a set. After generating all the subsets, print the size of the set obtained as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the Bitwise XOR// of every possible subsetunordered_set<int> s;// Function to generate all// combinations of subsets and// store their Bitwise XOR in set Svoid 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 arrayvoid 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 Codeint 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 approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Stores the Bitwise XOR// of every possible subsetstatic HashSet<Integer> s;// Function to generate all// combinations of subsets and// store their Bitwise XOR in set Sstatic 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 arraystatic 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 Codepublic 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 subsets = set([]) # Function to generate all# combinations of subsets and# store their Bitwise XOR in set Sdef 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 arraydef 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 CallmaxSizeSet(arr, N)# This code is contributed by decode2207. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Stores the Bitwise XOR// of every possible subsetstatic HashSet<int> s;// Function to generate all// combinations of subsets and// store their Bitwise XOR in set Sstatic 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 arraystatic 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 Codepublic 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 subsetlet s;// Function to generate all// combinations of subsets and// store their Bitwise XOR in set Sfunction 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 arrayfunction 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 Codelet arr=[1, 2, 3, 4, 5 ];let N = arr.length;// Initialize sets = new Set();// Function CallmaxSizeSet(arr, N);// This code is contributed by avanitrachhadiya2155</script> |
Output:
8
Time Complexity: O(NN)
Auxiliary Space: O(N)
Efficient approach: The above approach can be optimized by using the Greedy Approach and Gaussian Elimination. Follow the steps below to solve the problem:
- Initialize an auxiliary array, say dp[] of size 20, that stores the mask of each array element and initializes it with 0.
- Initialize a variable, say ans as 0, to store the size of the array dp[].
- Traverse the given array arr[] and for each array element arr[], perform the following steps:
- Initialize a variable, say mask as arr[i], to check the position of the most significant set bit.
- If the ith bit from the right of arr[i] is set and dp[i] is 0, then update the array dp[i] as 2i and increment the value of ans by 1 and break out of the loop.
- Otherwise, update the value of the mask as the Bitwise XOR of the mask and dp[i].
- After completing the above steps, print the value of 2ans as the resultant size of the required set of elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int const size = 20;// Stores the mask of the vectorint dp[size];// Stores the current size of dp[]int ans;// Function to store the// mask of given integervoid 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 arrayvoid 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 Codeint 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 approachclass 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 vectordp = [0]*20# Stores the current 20 of dp[]ans = 0# Function to store the# mask of given integerdef 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 arraydef maxSizeSet(arr, N): # Traverse the array for i in range(N): insertVector(arr[i]) # Print the answer print ((1 << ans))# Driver Codeif __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 approachusing System;class GFG{ static int size = 20;// Stores the mask of the vectorstatic int[] dp = new int[size];// Stores the current size of dp[]static int ans;// Function to store the// mask of given integerstatic 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 arraystatic 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 codepublic 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 approachlet size = 20;// Stores the mask of the vectorvar dp = new Array(size).fill(0);// Stores the current size of dp[]let ans = 0;// Function to store the// mask of given integerfunction 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 arrayfunction maxSizeSet(arr, N){ // Traverse the array for(let i = 0; i < N; i++) { insertVector(arr[i]); } // Print the answer document.write(1<<ans);}// Driver Codelet arr = [ 1, 2, 3, 4, 5 ];let N = arr.length;// Function CallmaxSizeSet(arr, N);// This code is contributed by nitin_sharma </script> |
Output:
8
Time Complexity: O(M * N)
Auxiliary Space: O(M * N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
