 # DOR - Editorial

Thanks for the tip bro .

You are welcome .

Default pow function returns double. So it doesn’t handle large numbers

https://www.codechef.com/viewsolution/27518791
can anyone suggest why i m getting WA

Given that R = 0 is a possibility, you must first realize that the loop at `line 17` is going to
Go on and on.... Geeks for Geeks solution doesn’t work with 4th example in question. This is the correct version [Python]:

``````t = int(input())

for _ in range(t):
x,y = map(int,input().split())
z = x^y
msbPos = 0
while(z):
msbPos +=1
z>>=1

maxXor, two = 0,1

while y:
res = y%2

if msbPos:
maxXor += two                # till msbPos all values will be 1's
msbPos -= 1
else:
maxXor += two*res        #before msbPos in y, values can be 0 or 1

two <<=1
y = y//2

print(maxXor)``````

ok thanks for helping
i have added a conditon for that
but its still showing WA

1 Like

I think your code is perfect till `line 26`. Now, `i` stores the position of the highest set bit of `r`, considering that the LSB is at position `0`. The don’t quite understand the logic that follows afterwards. You are only left with 2 simple steps:

1. `x` is the `i`-th bit of `l` and `y` is the `i`-th bit of `r`. While `x` equals `y`, you `OR` either of the two with `a` and decrement `i`. Do so till either `i` reaches `0` or `x` does not equal `y`.

2. Now that we have injected the longest identical prefix of `l` and `r` into `a`, all that’s left is to `OR` a string of set bits of length `i + 1` with `a`.

I think the editorial has done a good job explaining why this works. Hope this helps. 1 Like

@nkvg2015

Heavily Documented Implementation here: https://www.codechef.com/viewsolution/27526514

Some cliffnotes:

1. I extensively used >> and << operators.
2. I got a massive hint about solving the problem by doing the problem thanks to the fourth test case. (Although I solved it in practice). This can be quite useful if the testcases supplied to us are “nice”.

I converted 1000000000123, 1000000123456, 1000000192511 to binary. Here I observed that the final answer in binary is as follows:
"111010001101010010100"“1111111111111111111”. That lead me to the pattern quickly that all common leading bits are to be retained and all bits that follow are to be set.

7 Likes

for AND here u go
see my article : https://www.geeksforgeeks.org/maximum-bitwise-and-pair-from-given-range/

1 Like

Mine Article … 3 Likes

yes,when we take both integers as R .

figured out that “AND” of two numbers will always be less than or equal to least of those two numbers.

I am doing same thing but getting wrong answer, please anyone help
here is my code

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
long long int l,r;
cin>>l>>r;
long long int ans=0;
int i;

``````    int bit=log2(r);
bit+=1;
int a[bit]={0},b[bit]={0},c[bit];
for(i=0;i<bit;i++)
{
a[i]=r%2;
r=r/2;

b[i]=l%2;
l=l/2;
}

for(i=bit-1;i>=0;i--)
{
if(a[i]==b[i])
c[i]=a[i];
else
break;
}
for(i;i>=0;i--)
{
c[i]=1;
}

for(i=0;i<bit;i++)
{
ans=ans+pow(2,i)*c[i];
}

cout<<ans<<endl;
}
return 0;
``````

}

no anand if we take 5 with binary 101 ans 2 with binary as 010 if we go according to u we would get ans as 5 ie 101 but here ans is 7 ie 111

I said about the ‘AND’ case , not the xor Sir.

I specified my comment for ‘’ AND ", not “OR”.

can someone tell me why im getting wrong output . i did exactly like editorial and all test cases are also passed my solution

Thanks ! It helped so much!

1 Like