Count of Subsets having Maximum Possible XOR Value

Approach 1

We can divide the problem into two parts:

1. Finding the maximum XOR value among all possible non-empty subsets of the given array 'ARR'.
2. Counting the number of subsets with the XOR of its elements equal to the one found in the previous part.
    

Maximum XOR value

Using the standard Gaussian Elimination Algorithm, we find the maximum XOR value among all subsets of the given array 'ARR' in O(N) time complexity. Gaussian Elimination Algorithm consists of the following steps:

1. Let the number of bits in the maximum element of the array be 'MSB'.
    
2. Assign 'INDEX' = 0.
    
3. Iterate 'IND' from MSB to 0 and do the following:
   1. Iterate from 'INDEX' to N - 1 and find the maximum element with the bit at the 'IND' index as set and let its index be 'MAX_ELEM_INDEX'.
   2. If there exists no such element, continue.
   3. Swap 'ARR[INDEX]' and 'ARR[MAX_ELEM_INDEX]'.
   4. Do the bitwise XOR of each element in the array with set bit at 'IND' index with 'ARR[NDEX]'.
   5. Increment 'INDEX'.
       
4. Finally, the maximum XOR of any subset is the xor of the array elements. As you can notice, we are modifying the array in 3.d.
    

Counting subsets with maximum XOR value

One straightforward approach is to consider all possible subsets of the given array and calculate the XOR of the subset elements. If it equals the maximum XOR value, increment the count by one.

Algorithm

1. Assign 'MAX_XOR' = 0. Find the maximum XOR value using the technique described above and store it in 'MAX_XOR'.
    
2. Do a for loop with variable i from 1 to 2 ^ N - 1 and execute the following statements:
   1. Assign 'TEMP_XOR' = 0.
   2. Start a for loop with variable j from 0 to N - 1 and do the following:
      1. If j & (1 << i) is greater than 0, it implies j is included in the current subset. Thus update 'TEMP_XOR' = 'TEMP_XOR' ^ 'ARR[j]'.
   3. If 'TEMP_XOR" equals 'MAX_XOR', increment the count by one.
       
3. Return the count.

C++ implementation

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int findMaxXor(int N, vector<int> &arr, int MSB){

   // Initialize required variables.
   int index = 0;
   int maxElemIndex = -1;
   int maxElem = INT_MIN;

   for(int i = MSB; i >= 0; i--){

       // Find the index of the maximum element with ith bit set.
       for(int j = index; j < N; j++){
           if(arr[j] > maxElem && (arr[j] & (1 << i)) > 0){
               maxElem = arr[j];
               maxElemIndex = j;
           }
       }

       // If there is no maximum element.
       if(maxElemIndex == -1){
           continue;
       }

       // As described in the approach.
       swap(arr[index], arr[maxElemIndex]);

       maxElemIndex = index;
       index++;

       // Update array elements with ith bit set except the just found element itself.
       for(int j = 0; j < N; j++){
           if((arr[j] & (1 << i)) && j != maxElemIndex){
               arr[j] ^= arr[maxElemIndex];
           }
       }

       // Updates for the next iteration.
       maxElemIndex = -1;
       maxElem = INT_MIN;
   }

   // Maximum xor value is the XOR of the array elements left.
   int maxXor = 0;
   for(int i = 0; i < N; i++) maxXor = maxXor ^ arr[i];

   // Return the output.
   return maxXor;
}

int countMaxXorSubsets(int N, vector<int>& arr){
  
   // To hold the count of required subsets.
   int countSubs = 0;

   // Maximum element and bits in it.
   int maxElem = INT_MIN;
   int countBits = 0;
  
   // Find the maximum element and calculate the number of bits in it.
   for(int i = 0; i < N; i++) maxElem = max(maxElem, arr[i]);
   while(maxElem > 0){
       countBits++;
       maxElem >>= 1;
   }

   // Find maximum XOR as explained in the approach.
   int maxXor = findMaxXor(N, arr, countBits);

   // Consider all possible non-empty subsets.
   for(int i = 1; i < (1 << N); i++){
      
       // Xor of the current subset.
       int tempXor = 0;
       for(int j = 0; j < N; j++){
           if((i & (1 << j))){
               tempXor ^= arr[j];
           }
       }

       // If the current subset has the maximum xor.
       if(tempXor == maxXor){
           countSubs++;
       }
   }

   // Return the count.
   return countSubs;
}

int main(){

   // Input the size of N.
   int N;
   cout<<"Enter the value of N: ";
   cin>>N;

   // Input the array elements.
   vector<int> arr(N);
   cout<<"Enter the elements: ";
   for(int i = 0; i < N; i++){
       cin>>arr[i];
   }

   // Output the count of such subsets.
   int countSubs = countMaxXorSubsets(N, arr);
   cout<<countSubs<<endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the value of N: 3
Enter the elements: 9 8 5

You can also try this code with Online C++ Compiler

Run Code

Output

1

You can also try this code with Online C++ Compiler

Run Code

Complexities

Time Complexity

The time complexity of the above approach is O(2 ^ N), where 'N' is the size of the given array.

It is because the number of different non-empty subsets of an array of size 'N' is equal to 2 ^ N. The time complexity of finding the maximum XOR value is O(N) which is lower than O(2 ^ N).

Space Complexity

The space complexity of the above approach is O(1).

As we are using constant space to execute the algorithm.

Also see, Euclid GCD Algorithm

Approach 2

In this approach, we will discuss an efficient strategy to count the number of subsets with the maximum XOR value.

We will initialize a variable 'M' with the maximum XOR value possible in any subset of the array 'ARR'. We will be using dynamic programming to count the number of subsets progressively.

Next, we create a 2-dimensional array 'DP[N + 1][M + 1]'. Here, 'DP[i][j]' describes the count of subsets of ARR[0..i-1] with XOR value j.

Initial State of the DP array:

Initialize all the positions in the 'DP' array with 0 and assign 'DP[0][0]' = 1 since XOR of an empty set is 0.

Transition Statement:

DP[i][j] = DP[i­ - 1][j] + DP[i­ - 1][j ^ ARR[i - 1]]

If there is a subset ARR[0...i - 2] with the XOR value j, then there is also a subset ARR[0...i - 1] with the XOR value j. Also, if there is a subset arr[0....i-2] with the XOR value jarr[i], then there must be a subset arr[0...i-1] with the XOR value j, because j ^ arr[i-1]^ arr[i-1] = j.

Output:

'DP[N][M]', since 'DP[i][j]' is the number of subsets from arr[0..i-1] with j as XOR value, and 'DP[N][M]' is the number of subsets from the array ARR[0..N-1] with XOR value of 'M'.

Algorithm

1. Assign 'MAX_XOR' = 0. Find the maximum XOR value, same as in the previous approach.
2. Create a 'DP' array as 'DP[N + 1][MAX_XOR]' and update the initial state.
3. All dp[i][j] values should be set to 0.
4. Because the XOR of an empty set is 0, the value of dp[0][0] = 1.
5. Fill the dp array as following:
   1. for i = 1 to N'': 
      1. for j = 0 to 'MAX_XOR': 
         1. dp[i][j] = dp[i­-1][j] + dp[i­-1][j^arr[i-1]].
6. Return 'DP[N][MAX_XOR]'.

C++ implementation

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int findMaxXor(int N, vector<int> arr, int MSB){

   // Initialize required variables.
   int index = 0;
   int maxElemIndex = -1;
   int maxElem = INT_MIN;

   for(int i = MSB; i >= 0; i--){

       // Find the index of the maximum element with ith bit set.
       for(int j = index; j < N; j++){
           if(arr[j] > maxElem && (arr[j] & (1 << i)) > 0){
               maxElem = arr[j];
               maxElemIndex = j;
           }
       }

       // If there is no maximum element.
       if(maxElemIndex == -1){
           continue;
       }

       // As described in the approach.
       swap(arr[index], arr[maxElemIndex]);

       maxElemIndex = index;
       index++;

       // Update array elements with ith bit set except the just found element itself.
       for(int j = 0; j < N; j++){
           if((arr[j] & (1 << i)) && j != maxElemIndex){
               arr[j] ^= arr[maxElemIndex];
           }
       }

       // Updates for the next iteration.
       maxElemIndex = -1;
       maxElem = INT_MIN;
   }

   // Maximum xor value is the XOR of the array elements left.
   int maxXor = 0;
   for(int i = 0; i < N; i++) maxXor = maxXor ^ arr[i];

   // Return the output.
   return maxXor;
}

int countMaxXorSubsets(int N, vector<int>& arr){

   // Maximum element and bits in it.
   int maxElem = INT_MIN;
   int countBits = 0;
  
   
   for(int i = 0; i < N; i++) maxElem = max(maxElem, arr[i]);
   while(maxElem > 0){
       countBits++;
       maxElem >>= 1;
   }


   int maxXor = findMaxXor(N, arr, countBits);

   int dp[N+1][maxXor+1];
  
  
   for (int i=0; i<=N; i++)
       for (int j=0; j<=maxXor; j++)
           dp[i][j] = 0;
  
   dp[0][0] = 1;
   // Fill the dp table.
   for (int i=1; i<=N; i++)
       for (int j=0; j<=maxXor; j++)
           dp[i][j] = dp[i-1][j] + dp[i-1][j^arr[i-1]];
   
   return dp[N][maxXor];
}

int main(){

   // Input the size of N.
   int N;
   cout<<"Enter the value of N: ";
   cin>>N;

   // Input the array elements.
   vector<int> arr(N);
   cout<<"Enter the elements: ";
   for(int i = 0; i < N; i++){
       cin>>arr[i];
   }

   // Output the count of such subsets.
   int countSubs = countMaxXorSubsets(N, arr);
   cout<<countSubs<<endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the value of N: 3
Enter the elements: 9 8 5

Output

1

Complexities

Time Complexity

The aforementioned technique has an O(N * M) time complexity, where 'N' is the size of the provided array and 'M' is the maximum XOR value. It is because we are using two nested for loops with 'N' and 'M' as limits in the dynamic programming approach.

Space Complexity

Because we are utilizing a 2-dimensional array 'DP' of size N * M, the space complexity of the aforementioned technique is O(N * M).

Read about Bitwise Operators in C here.

Frequently Asked Questions

What distinguishes Dynamic Programming from other approaches?

The solutions for smaller instances are used to solve a larger instance, because the solutions to a smaller instance may be needed more than once, keep the results in a table. As a result, each smaller instance is only solved once. To save time, more space is used.

What are some examples of dynamic programming applications?

Google maps: Consider the fact that we must commute from home to work every day.

Longest common subsequence: The term "longest" refers to the sequence that is the longest of all the subsequences. The term "common" refers to when two strings are given and we must locate the common thread between the two subsequences.

Knapsack problem: ​​The problem is divided into subproblems, and these subproblems are further divided into subproblems in the divide-and-conquer technique. This division procedure will continue until we reach a subproblem that is easily addressed. We may run across the same subproblems several times during this approach.

What is the XOR operation?

The XOR operation is the operation in which we take two different boolean inputs and the output is true only if both the inputs are different from each other.

What is a subset of an array?

The subset of an array is a set of elements from the array itself. If we’re making a subset of an array, for each element in the array, we have a choice of whether to include that number in the subset or not.

Conclusion

We solved an interesting problem by dividing it into two subparts in this blog. While the solution to the first problem is well-known in the coding community, we brainstormed to solve the second part as efficiently as possible. We realized that the time complexity of the brute force approach is exponential and solved in almost linear time complexity using the dynamic programming approach.

Hence learning never stops, and there is a lot more to learn.

Recommended Problems: 

• Number Of Subsets
• Subset Sum Equal To K
• Minimum Subset Sum Difference
   

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!