Find the number of subsets of an array having a given XOR value

Reading time: 30 minutes | Coding time: 10 minutes

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the xor value of all elements in the subset. This can be solved using Dynamic Programming in linear time.

Example:

Input: arr[] = {1, 2, 3, 4}, M = 4
Output: 2
The subsets are:

{4}, {1, 2, 3, 4}

The XOR of other subsets like {1, 2, 3} or {1, 3} is not 4 and hence, these subsets are not included in our count.

We will solve this using two approaches:

• Naive approach O(2^N) time
• Dynamic Programming (N * K) time

Approach	Time	Space
Naive/ Brute force	O(2^N)	O(1)
Dynamic Programming	O(N * K)	O(N * K)

Naive approach O(2^N)

In naive approach we find all the subsets of the given array by recursion and find xor of all elements present in them and count how many xor values are equal to m.

The time complexity of such a technique is O(2^length) where length signifies the length of the given array.

Efficient approach O(N * K)

We will use Dynamic programming approach to solve this problem efficiently. The working will be similar to what we did in Number of subsets with sum divisible by M.

In the table DP[i][j] signifies number of subsets with xor j till the elements from 1st to ith are taken into consideration.

DP[i][j] = number of subsets with XOR 'j' till the elements from 1st to ith

Formula used-:

DP[i][((j-1)^arr[i-2])+1] = 
         DP[i-1][((j-1)^arr[i-2])+1] + DP[i-1][j];

If we are at ith element of the array and traverse the row for the (i-1)th element we get the subsets number of subsets of all possible xor values.

For the ith element if we get DP[i-1][j]>0 it means that xor value j-1 has that many number of subsets. So we take xor of arr[i] with this value and get the resulting number of subsets of the new xor value (say x) by adding the previous number of subsets of x which will be given by DP[i-1][((j-1)^arr[i-2])+1] and number of subsets of value j-1 which is equal to DP[i-1][j].

For generating the values in DP table we take DP[1][1]=1 which represents there is always a null subset having xor value 0. This will be the base case for the approach USED.

Implementation

The maximum possible xor value of any subset will be pow(2,((log2(max(arr))+1))) – 1. Let this number be equal to k.

So we take the number of columns of the 2-D array to be k+2 and number of rows to be N+2. Now we define the array as DP[N+2][k+2].

For the given example:

arr[]={1,2,3,4}
k=pow(2,log2(4)+1)-1=7

-1	0	1	2	3	4	5	6	7
-1	1	0	0	0	0	0	0	0
1	.	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.	.
4	.	.	.	.	.	.	.	.

We set DP[1][1]=1 as there is always a subset i.e. (null set) which has xor value=0.

Now start traversing the array from i=2 and for each DP[i][j] we check if DP[i-1][j]>0 we go to element DP[i][j^arr[i-2]+1) and increase it's value by DP[i-1][j]+DP[i-1][j^arr[i-2]+1] as now the subset count of j^arr[i-2] will increase by the number of subsets having xor value as j.

Stepwise visualization of DP table

• We traverse the given array and update the values in the DP table accordingly.Like arr[0]=1 so we check which subset value in the above row has frequency>0 here it is 0 so we update the value of DP[2][0^1+1] by DP[1][1]+DP[1][2].

-1	0	1	2	3	4	5	6	7
-1	1	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0
2	.	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.	.
4	.	.	.	.	.	.	.	.

• Likewise we do it for arr[1]=2.

-1	0	1	2	3	4	5	6	7
-1	1	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0
2	1	1	1	1	0	0	0	0
3	.	.	.	.	.	.	.	.
4	.	.	.	.	.	.	.	.

• Likewise for arr[2]=3

-1	0	1	2	3	4	5	6	7
-1	1	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0
2	1	1	1	1	0	0	0	0
3	2	2	2	2	0	0	0	0
4	.	.	.	.	.	.	.	.

• Likewise for arr[3]=4

-1	0	1	2	3	4	5	6	7
-1	1	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0
2	1	1	1	1	0	0	0	0
3	2	2	2	2	0	0	0	0
4	2	2	2	2	2	2	2	2

C++ Implementation

Following is the C++ Implementation of our Dynamic Programming approach:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll arr[]={1,2,3,4};
    ll m=4;
    ll i,j,l=4;
    ll max_ele=0;

    //Calculating the maximum possible xor value
    for(i=0;i<l;i++)
    {
        max_ele=max(max_ele,arr[i]);
    }
    int k=(1 << (int)(log2(max_ele) + 1) ) - 1; 
    ll DP[l+2][k+2]={0};
    DP[0][0]=-1;
    DP[1][0]=-1;
    //filling all possible xor values in the first row
    for(i=1;i<k+2;i++)
    {
        DP[0][i]=i-1;
        DP[1][i]=0;
    }
    //filling all the array elements in the first column
    for(i=2;i<l+2;i++)
    {
        DP[i][0]=arr[i-2];
    }
    DP[1][1]=1;
    //Filling the DP table
    //according to given logic
    for(i=2;i<l+2;i++)
    {
        for(j=1;j<k+2;j++)
        {
            if(DP[i-1][j]!=0)
            {
                DP[i][((j-1)^arr[i-2])+1] = 
                    DP[i-1][((j-1)^arr[i-2])+1]+DP[i-1][j];
            }
        }
        for(j=1;j<k+2;j++)
        {
            DP[i][j]=max(DP[i-1][j],DP[i][j]); 
        }  
    }
    for(i=0;i<l+2;i++)
    {
        for(j=0;j<k+2;j++)
        {
            cout<<DP[i][j]<<"\t";
        } 
        cout<<"\n";
    }

    //counting the number of subsets
    //having given xor value
    ll ans=DP[l+1][m+1];
    cout<<"Number of subsets is:"<<ans<<"\n";
    return 0;
}

Output:

Number of subsets is:2

Complexity

The time complexity of the given approach is O(k * n) where k is the maximum possible xor value and n is the total number of elements in the array.

The space complexity of our approach is O(N * K) as well.

Following is the summary:

Approach	Time	Space
Naive/ Brute force	O(2^N)	O(1)
Dynamic Programming	O(N * K)	O(N * K)

With this, you have the complete knowledge of this problem. Enjoy.