can someone intelligent explain me why the code fails in testcase 8 to 14 if i place a “+” in the 12th line of my code if i place “|” or operator it works fine.

https://www.codechef.com/viewsolution/26237730

# XORSUB conceptual doubt

“+” and | aren’t interchangeable.

They are different. + will add 2 numbers, in binary representation if 2 corresponding bits are 1, then 1+1 will give 0 and carry=1, which will be added on the next significant bit. | is just bitwise OR, it’ll take “OR” of corresponding bits into the result.

SO, in short, | is simply “+”, without the carries.

It would have been better if you had understood the context of his question before commenting. His dp states store boolean values. Now `dp[something] = dp[something-else] + dp[something-something-else]`

is what he replaced `dp[something] = dp[something-else] | dp[something-something-else]`

by. Now addition of dp[something-else] and dp[something-something-else], ie `dp[something-else] + dp[something-something-else]`

will always be either 0, 1 or 2, because both of them can either be False(0) or True(1), and since the variable their sum is assigned to is also boolean, the result stored in it is also either 1(True), 2(True) or 0(False). So, at-least in this case, + and | seems equivalent as

True | True -> True

and True -> converts to 1, 1 + 1 = 2 -> converts to True in boolean

You can extend this to False and it’s equivalent 0 and see it still holds.

The problem, in my opinion, is somewhat different. Perhaps @ssjgz or @l_returns can clarify.

Edit- @adi521, the only thing you missed here is that you declared your dp array of type integer, that’s what causing the problem. + and | will only be equivalent when dp array is of type boolean. I replaced int with bool in your code and kept + as it is(not changing it to |), and all the test cases passed- https://www.codechef.com/viewsolution/26240937

It’s fairly easy to trigger an overflow in your `dp[i][j]`

value (see e.g. this testcase), which probably doesn’t help matters

Edit:

Since this thread is about “why” the results differ: as far as I can tell, the *only* functional problem changing `|`

to `+`

in your original solution causes is overflow. It’s quite possible (though inadvisable) to get correct results by simply avoiding overflow by e.g. clamping `d[i][j]`

to be at most `std::numeric_limits<int>::max() / 2`

after computing it - if we do this, then the solution with `+`

*should* give the same results as the solution with `|`

.

But as @silver_surfer says, the best approach is simply to use `bool`

instead of `int`

and avoid all these headaches entirely

yaa might be a problem of over flow but still n is small …i will check by declaring it long…n thanks bro for help

that means if the dp array is of long type then it will give correct result

Not necessarily - if you’re dealing with exponentially larger numbers, you can easily overflow a long, too.

Edit:

Which is the case, here - here is some of the final output with some diagnostics added before an overflow occurs:

```
<snip>
i: 71 j: 511 dp[i][j]: 4611686018427387904
<snip>
```

The next line is

```
i: 72 j: 0 dp[i][j]: -9223372036854775808
```

The maximum value a `long`

can hold on my computer is just `9223372036854775807`

.

but i dont think thats the issue as n is not that large and even ai is not that large

It *is* an issue - those printouts showing the overflow came from your code plus my testcase - I just added some print statements to it!

Edit:

Here’s a copy of your code with the following modification:

a) Changed the types from `int`

to `long`

b) Keep track of the largest value of `dp[i][j]`

, and print it out when it increases

c) Print out negative values of `dp[i][j]`

, indicating overflow.

Run it with the testcase I linked and observe the output.

```
#include <bits/stdc++.h>
using namespace std;
int fun(int a[],int n,int k)
{
long dp[n+1][1024],i,j,val=0,w=-1;
long largestDPSeen = 0;
for (i=0; i<=n; i++)
{for (j=0; j<=1023; j++)
dp[i][j] = 0;}
dp[0][0]=1;
for (i=1; i<=n; i++)
{for (j=0; j<=1023; j++)
{
dp[i][j] = dp[i-1][j] + dp[i-1][j^a[i-1]];
if (dp[i][j] > largestDPSeen)
{
largestDPSeen = dp[i][j];
cout << "New largestDPSeen: " << largestDPSeen << endl;
}
if (dp[i][j] < 0)
{
cout << "Whoops - overflow: " << dp[i][j] << endl;
}
}
}
for(i=1023;i>=0;i--)
{
if(dp[n][i]>0)
w=max(w,i^k);
}
return w;
}
int main() {
// your code goes here
int t,i;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
cout<<fun(a,n,k)<<"\n";
}
return 0;
}
```