Xor profit problem

#1

how to approach with O(n) complexity ?

#2

An efficient solution is to consider pattern of binary values from L to R. We can see that first bit from L to R either changes from 0 to 1 or it stays 1 i.e. if we take the XOR of any two numbers for maximum value their first bit will be fixed which will be same as first bit of XOR of L and R itself.
After observing the technique to get first bit, we can see that if we XOR L and R, the most significant bit of this XOR will tell us the maximum value we can achieve i.e. let XOR of L and R is 1xxx where x can be 0 or 1 then maximum XOR value we can get is 1111 because from L to R we have all possible combination of xxx and it is always possible to choose these bits in such a way from two numbers such that their XOR becomes all 1. It is explained below with some examples,

eg:
L = 8 ( 1000 ) R = 20(10100)

xor would give
11100
msb of L^R is 10000 ( 5th position )
this implies that
a combination occurs b/w l & r which would fetch us the value with all 11111 ( => 15 & 16 )

#3
#4

if we take the XOR of any two numbers for maximum value their first bit will be fixed which will be same as first bit of XOR of L and R itself, I can’t understand the approach
if we take 8 and 9, then first bit of their xor will be 0, and first bit of l ^ r will be 1

#5

8 (1000)
9( 1001)
xor = 1001
first bit means most significant bit
then there exists
1000 ^ 0111 === 1111 =>( 8 ^ 7)

1 Like