I hope u all doing good, During the whole contest. I am just thinking about it after solving the first two. Try different approaches but nothing works.Is this Dp or direct formula,Hint please?

I am pretty sure it is not dp

just greedy

```
ntest = int(raw_input())
for test in range(ntest):
A,B = [int(x) for x in raw_input().split()]
bin_B = bin(B)[2:]
bin_A = bin(A)[2:]
lb = len(bin_B)
while (len(bin_A) < lb):
bin_A = '0' + bin_A
X = 0
i = 0
while (i < lb and bin_A[i] == bin_B[i]):
i+=1
while i <= lb:
X += int(pow(2,lb-1-i))
i +=1
print X | B
```

Can you tell the logic?

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

Can anyone explain this solution. And why is the value of c 576460752303423488

Its pure binary search.

What I found out was:

That maximum can only be found when all bits are set.

So suppose you have L = 16, R = 31.

We apply binary search on it, so mid will be 23.

Now, we check on two conditions:

```
1) mid > l
2) mid <= r
```

If yes, answer is

`((mid) | (mid - 1))`

If no, apply binary search with a bit of a modification and you will get it.

I had proved it myself, you can also see, it works. You just need to look into edge cases.

If there is a transition point from â€śone 2 power numberâ€ť to â€śanother two power numberâ€ť, then you can always make all bits 1.

Because during the transition for example,

(2^3) - 1 = 7 which is 111 in binary

(2^3) = 8 (transition happened to 4 bits). Hence 8â€™s binary is 1000

Hence OR = 0111|1000 => 1111

This is 1 part of the solution.

My logic seems correct but I got a TLE and couldnâ€™t think of a faster method.

I flip the bits of the max number Â®. If that value is < L, then I keep adding increasing powers of 2 ( like +2 + 2^2 + 2^3) so that it becomes just >= L and then take the bitwise OR of that number and R.

Can someone tell how to think about it better?

You had to find the number which lies between l and r , that converts the maximum number of zeroes in the binary of r from 0 to 1

For e.g if the binary of some number is 1000100110

then the maximum value bitwise OR can give is 111111111,

so any number with a 1â€™s in binary notations at the place 0â€™s in binary notation of r is valid

therefore take base case as binary of l , then compare it with binary of r

then turn the binary representation of l into 1â€™s wherever r has 0â€™s while also taking care not to make the number greater than r

First take binary equivalents of l and r (let l=1031 and r= 93714)

Then ans would be like : find first different bit then set all bits to 1 from that bit. And bits before that will be same as bits of r

eg:

93714 = 10110111000010010

1031 = 00000010000000111

The ans is : 11111111111111111 i.e. 131071 as first bit is different

if binary equivalent of l= 100101

and binary equivalent of r= 101010

then ans= 101111 as 3rd bit is different so all bits 1 from 3rd bit

i solved it like this:

starting from the highest bit down to 0th bit , compare that bit position of l and r at position i:

- if li==1 and ri==1, simply add (1<<i) to answer
- if li==0 and ri==1, for all bits position smaller than i add (1<<i) to answer and return it

the main thing was if li==0 and ri==1 there will definitely exists a number between l and r whose all bits are set from 0th bit to (i-1)th bit

My solution was, to check if the bits in binary representation of l and r are equal then the answer will have same bit, if at any point they become unequal then the rest of the bits in the answer are 1.

Example

```
1031 93714
>>> bin(93714)[2:]
'10110111000010010'
>>> bin(1031)[2:].zfill(17)
'00000010000000111'
>>>
```

Since the first bit is unequal the bits in the answer will all be 1

```
>>> bin(131071)[2:].zfill(17)
'11111111111111111'
```

```
1000000000123
'1110100011010100101001010001000001111011'
1000000123456
'1110100011010100101001101111001001000000'
1000000192511
'1110100011010100101001111111111111111111'
```

Solution link : https://www.codechef.com/viewsolution/27503957

Can anyone explain the 2nd test cases?

how will â€ś4 5â€ť , give â€ś5â€ť as output?

5|5 => 5 or with 5 gives you 5

If we do bitwise operations between

- 4 and 5
- 5 and 5

The answer to the above will be 5.

Try using bitset in c++ and see in l if itâ€™s bit can be changed to 1 so that l or r can give us 1 ,in this way check for all such bits but keeping in mind that it doesnâ€™t exceed r.

The two numbers would be **4 and 5**.

4 -> 100

5-> 101

The OR of the two numbers would be

101 , that is, 5