DOR - Editorial

editorial
, , , , ,
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();
	}

}

}

43

DjrmFx - Online C++0x Compiler & Debugging Tool - Ideone.com. can u please help me brother i am not getting y its wrong nd it is giving wa for 4th testcase.

44

why i m getting wrong answer in this.I have did exactly what explained in the editorial.Can anyone help.Here is link to my solution.
https://www.codechef.com/viewsolution/27637908

45

I am not able to understand the editorial. can someone please make it a bit more simple?

46

Great Editorial

47

But I have used ceil(pow(2,i)) but it is showing WA . then i changed to
(long long )(pow(2,i)+0.5) then got AC .
any idea why it is WA for first time

49

long long int ans = ceil(pow(2.5,4));
long long int ans2 = (pow(2.5,4) + 0.5);
cout <<ans << " " << ans2 << endl;

I think this must be self-explanatory. Run this and check out the output. You’ll learn about ceil.