DOR - Editorial

editorial
, , , , ,
23

You are welcome :smile:.

24

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

25

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

26

Given that R = 0 is a possibility, you must first realize that the loop at line 17 is going to
Go on and on.... :slightly_smiling_face:

27

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)
1 Like
28

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

1 Like
29

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. :slightly_smiling_face:

1 Like
30

@nkvg2015

Heavily Documented Implementation here: CodeChef: Practical coding for everyone

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
31

for AND here u go
see my article : Maximum Bitwise AND pair from given range - GeeksforGeeks

1 Like
32

Mine Article … :stuck_out_tongue_winking_eye:

3 Likes
33

yes,when we take both integers as R .

34

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

35

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;

}

36

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

37

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

38

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

39

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

40

Thanks ! It helped so much!

1 Like
41

Glad I could help!

42

What is wrong to my solution. Anyone please do try to figure, we can also use long instead of BigInteger. This solution is first finding log of L and R, then accordingly generated two nums (2^n - 1) will generate number with all bits set while 2^n will generate number with only one (MSB) bit set. then ORing is done. it is running for successfully for first three cases as explained in problem example but not for the last one.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

class DOR {

public static void main(String[] args) {
	try {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine().trim());
		for (int i = 0; i < T; i++) {
			String[] str = br.readLine().trim().split(" ");
			long L = Long.parseLong(str[0]);
			long R = Long.parseLong(str[1]);

			long biggest2Right = (long) ((Math.log(R)) / Math.log(2));
			long biggest2Left = (long) (Math.log(L) / Math.log(2));

			BigInteger bigInt;
			if (biggest2Right == biggest2Left) {
				bigInt = new BigInteger(String.valueOf(R));
			} else {
				bigInt = (new BigInteger(String.valueOf(2))).pow((int) biggest2Right);
				bigInt = (new BigInteger(String.valueOf(bigInt)))
						.or(new BigInteger(String.valueOf(bigInt.subtract(BigInteger.valueOf(1)))));
			}
			bw.write(String.valueOf(bigInt));
			bw.newLine();
		}
		// System.out.println(Long.MAX_VALUE >= 1000000000123);
		// System.out.println(Long.MAX_VALUE > Math.pow(10, 18));
		// System.out.println(Long.MAX_VALUE > Math.pow(10, 19));
		bw.close();
		br.close();
	} catch (Exception e) {
		e.printStackTrace();
	}

}

}