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 Bitwise OR value of all elements in the subset. This can be solved using Dynamic Programming in polynomial time.

Example:

Input: arr[] = {2, 4, 4}, M = 4
Output: 3

The subsets are:

{4}, {4}, {4,4}

We will solve this using two approaches:

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

Approach	Time	Space
Naive	O(2^N)	O(1)
DP	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 BitwiseOR of all elements present in them and count how many BitwiseOR 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 BitwiseOR j till the elements from 1st to ith are taken into consideration.

DP[i][j] = number of subsets with BitwiseOR j with elements 1 to j (index)

Our answer will be DP[K][N] where K is the given OR value and there are N elements in the array.

Formula used:

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

The key to this problem is to understand the above relation.

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 BitwiseOR values.

For the ith element if we get DP[i-1][j] > 0 it means that BitwiseOR value j-1 has that many number of subsets. So we take BitwiseOR of arr[i] with this value and get the resulting number of subsets of the new BitwiseOR 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 BitwiseOR value 0. This will be the base case for the approach used.

Implementation approach

Let us take maximum possible BitwiseOR value of any subset will be 1000. 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].

DP table for the given example-:

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

We set DP[1][1]=1 as there is always a subset i.e. (null set) which has BitwiseOR 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 BitwiseOR 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]=2 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|2+1] by DP[1][1]+DP[1][3].

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

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

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

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

-1	0	1	2	3	4	5	6
-1	1	0	0	0	0	0	0
2	1	0	1	0	0	0	0
4	1	0	1	0	1	0	1
4	1	0	1	0	3	0	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[]={2,4,4};
    ll m=4;
    ll i,j,l=3;

    int k=1000; 
    ll DP[l+2][k+2]={0};
    DP[0][0]=-1;
    DP[1][0]=-1;
    //filling all possible BitwiseOR 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 BitwiseOR value
    ll ans=DP[l+1][m+1];
    cout<<"Number of subsets is:"<<ans<<"\n";
    return 0; 
}

Output:

Number of subsets is:3

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	O(2^N)	O(1)
Dynamic Programming	O(N * K)	O(N * K)

HAPPY CODING!