Get this book -> Problems on Array: For Interviews and Competitive Programming

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.