Count distinct possible Bitwise XOR values of subsets of an array

0 0 11 minutes read

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 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>

Output:

Time Complexity: O(N^N)
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 i^th bit from the right of arr[i] is set and dp[i] is 0, then update the array dp[i] as 2ⁱ 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 2^ans 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 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>

Output:

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 zambiatek!