**Problem Links:**

**Setter** : Siddhant Gandhi

**Tester** : Jatin Nagpal

**Editorialist** : Siddhant Gandhi

**DIFFICULTY**

Easy - Medium

**PRE-REQUISITES**

Basic Math

**PROBLEM**

A mathematical expression consisting of binary bitwise operators( &, |, ^ ) is input as a string. Find out the maximum possible answer of this expression given that you can perform any operation first, that is you can violate precedence of operators.

**BRUTE FORCE( for PARTIAL marks )**

A brute force way to solve this problem would be solving the expression in all possible ways and then finding the maximum of the computed answers.

The number of ways in this case would be number of possible permutations of operators, here a permutation of operators would denote the sequence in which they are solved.

Let’s consider an expression **x1&x2^x3&x4** , here there are **3** operators, let’s number them as **1** , **2** and **3** respectively, then the permutation **(2, 1, 3)** means that we solve **2nd** operator first then the **1st** operator and finally the **3rd** one, so we first solve **(x2 ^ x3)** , then we solve **x1 & (x2 ^ x3)** and finally we solve **((x1 & (x2 ^ x3)) & x4).**

This approach would only fetch you partial marks, to head towards **AC** see the below given approach.

**HEADING TOWARDS AC!**

We can make this process more efficient by using this approach-

Let’s consider the same example again **x1&x2^x3&x4** .

The operands here are **[x1, x2, x3, x4]** , we now divide the operands into 2 different contiguous groups.

**Our aim is to solve all possible answers of 1st group with all possible answers of the 2nd group.**

The various possible groupings are-

**a) [x1] [x2, x3, x4]**

**b) [x1, x2] [x3, x4]**

**c) [x1, x2, x3] [x4]**

Let’s first solve for **a)** type grouping which is **[x1] [x2, x3, x4]** -

The only possible answer for **1st** group is **x1.**

**2nd** group can be further subdivided as-

**i) [x2] [x3, x4]**

**ii) [x2, x3] [x4]**

On solving **i)** we get **x2 ^ (x3 & x4).**

On solving **ii)** we get **(x2 ^ x3) & x4.**

So there are **2** possible answers of **2nd** group of **a)** which when solved with the only possible answer **x1** of **1st** group of **a)** results in **2** possible outcomes which are –

**x1 & (x2 ^ (x3 & x4))**

**x1 & ((x2 ^ x3) & x4)**

So the grouping of type **a)** results in 2 possible answers.

Let’s now solve for **b)** type grouping which is **[x1, x2] [x3, x4] –**

This need not be divided into further sub-groups as the only possible answer of **1st** group is –

**(x1 & x2)**

, and the only possible answer of **2nd** group is –

**(x3 & x4)**

So the **only** possible outcome of grouping of type **b)** is –

**((x1 & x2) ^ (x3 & x4))**

Finally we need to solve for **c)** type grouping which is **[x1, x2, x3] [x4] –**

This can solved in a similar way as grouping of type **a)** and would yield **2** possible outcomes.

So now we got **(2 + 1 + 2)** that is **5** possible answers out of which we need to compute the maximum.

The above solution would fetch you an **AC verdict** but it can be made even more efficient by using **Dynamic Programming** because there are various operations which are performed again and again on the same operands, so we **store** the result once it is computed.

**SOLUTION:**

## Setter

```
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
#define mod 1000000007
// 0 is &
// 1 is |
// 2 is ^
vector <int> b,c;
vector <int> dfs(int st,int en)
{
vector <int> ret;
if(st>en)
{
ret.push_back(b[st]);
return ret;
}
f(i,st,en+1)
{
vector <int> a=dfs(st,i-1);
vector <int> d=dfs(i+1,en);
for(int j: a)
{
for(int k: d)
{
if(c[i]==0)
ret.push_back(j&k);
else if(c[i]==1)
ret.push_back(j|k);
else
ret.push_back(j^k);
}
}
}
return ret;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
b.clear();
c.clear();
int n;
string a;
cin>>a;
n=a.length();
f(i,0,n)
{
if(a[i]<='9'&&a[i]>='0')
{
b.push_back(0);
int bs=b.size()-1;
while(a[i]<='9'&&a[i]>='0')
{
b[bs]=b[bs]*10+(a[i]-'0');
i++;
}
i--;
}
else
{
if(a[i]=='&')
c.push_back(0);
else if(a[i]=='|')
c.push_back(1);
else if(a[i]=='^')
c.push_back(2);
else
assert(1==2);
}
}
vector <int> an=dfs(0,b.size()-2);
int ans=0;
for(int i: an)
ans=max(ans,i);
cout<<ans<<'\n';
}
return 0;
}
```

## Tester(DP Solution)

```
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
#define mod 1000000007
// 0 is &
// 1 is |
// 2 is ^
vector <int> dp[101][101];
vector <int> b,c;
vector <int> dfs(int st,int en)
{
if(dp[st+1][en+1].size()!=0)
return dp[st+1][en+1];
vector <int> ret;
if(st>en)
{
ret.push_back(b[st]);
return dp[st+1][en+1]=ret;
}
f(i,st,en+1)
{
vector <int> a=dfs(st,i-1);
vector <int> d=dfs(i+1,en);
for(int j: a)
{
for(int k: d)
{
if(c[i]==0)
ret.push_back(j&k);
else if(c[i]==1)
ret.push_back(j|k);
else
ret.push_back(j^k);
}
}
}
// sort(ret.begin(),ret.end());
// unique(ret.begin(), ret.end());
return dp[st+1][en+1]=ret;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
f(i,0,101)
f(j,0,101)
dp[i][j].clear();
b.clear();
c.clear();
int n;
string a;
cin>>a;
n=a.length();
f(i,0,n)
{
if(a[i]<='9'&&a[i]>='0')
{
b.push_back(0);
int bs=b.size()-1;
while(a[i]<='9'&&a[i]>='0')
{
b[bs]=b[bs]*10+(a[i]-'0');
i++;
}
i--;
}
else
{
if(a[i]=='&')
c.push_back(0);
else if(a[i]=='|')
c.push_back(1);
else if(a[i]=='^')
c.push_back(2);
else
assert(1==2);
}
}
vector <int> an=dfs(0,b.size()-2);
int ans=0;
for(int i: an)
ans=max(ans,i);
cout<<ans<<'\n';
}
return 0;
}
```

**COMPLEXITY**

Complexity is roughly **O( Catalan number ).**

Assuming N is number of operators:-

Equation for calculating T(N) :-

T(N) = (T(N - 1) * T(0)) + (T(N - 2) * T(1)) + (T(N - 3) * T(2)) + … + (T(0) * T(N - 1)); Given T(0) = 1

For DP solution it’s T(N) + 2 * T(N - 1) + 3 * T(N - 2) + … + (N + 1) * T(0)

For non-DP solution, it’s sum of complexities of all the nodes in the tree formed by T(N)-

Ex:

`T(2) / \ T(1)*T(0) : T(0)*T(1) /\ /\ T(0) T(0) T(0) T(0)`

Ans = 2+4*1+4*1 = 10 ( T(2)=2,T(1)=1,T(0)=1 )

Feel free to share your approach.