CODEWITHSUNDEEP
algorithmbit-manipulation
thoughtful me
thoughtful me

Reputation: 115

Two values from range having maximum xor

We are given two constraint L and R(L<=R) and we have to find two values i and j(l<=i<=j<=R) such that Xor of them is maximum.

I already tried O(n^2) so want anything better.

Upvotes: 0

Views: 870

Answers (2)

vish4071
vish4071

Reputation: 5277

Here is the solution that you can use (This gives you answer in log(R))

Let me explain it with an example:

Let L=34, R=45. Represent them as bit-arrays:

L = 100010     R = 101101

You start from the left till you find the first mismatch of the form:

L[i] = 0 and R[i] = 1

You will always find this because L < R. (If L==R, this is trivial case and answer is 0)

From here on, change every bit of L to 1 and every bit of R to 0.

The numbers you get will be your i and j and their XOR will be the max you can get.

eg. 34 and 45

  100010 and 101101
1st mismatch at index 2 [0-based] 
From there, change all L[i] to 1 and all R[i] to 0
=> i = 100111 and j = 101000
=> i = 39 and j = 40
and i^j = 15

Upvotes: 3

iggy
iggy

Reputation: 1743

If this is a one time request, with no preprocessing:

Given a range [L, R] you just need to be able to find a number that has 1 at a particular bit position among the numbers in this range. This can easily be done with bit operations.

suppose you have L = 0, R = 7, in binary your numbers are:

000, 001, 010, ..., 111

the current number is 000, to maximize xor you need to find the number which has 1 at the most significant bit position. The first such number is 4 = 100. Now you are dealing with range 100, 101, ..., 111 and bit at the second highest position. The bit at the second highest position is 0, so to maximize xor you again need a number with a 1 on that position. The first such number is 6 = 110. You can apply the very same pattern again. Now that you are done with 000 you can do the same for 001 and so on.

The number of iterations for one number is the maximum number of bits you have in numbers from L to R. Hence the total number of operations is O((R-L+1)*log(R-L+1))

Upvotes: 1

Related Questions