Maximize xor

Easy

0/40

Average time to solve is 15m

Contributed by

28 upvotes

Asked in companies

Problem statement

You have an integer array ‘A’ of the form of [x, x+1, x+2, x+3, …….]. As the array is vast in size, you are given both endpoints of the array, i.e., If you are given two integers, ‘L’ and ‘R’, the array ‘A’ will be [L, L+1, L+2, ……., R-1, R]. Your task is to find the maximum possible value of ‘X’ such that the following two conditions hold.

a ⊕ b = X, where ⊕ denotes bitwise xor operation.
Both numbers ‘a’ and ‘b’ belong to the array ‘A’.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains 'T', denoting the number of tests.
For each Test :
    The only line contains two space-separated integers 'L' and 'R', denoting the endpoints of the array.

Output Format:

For each test, print an integer, denoting the maximum possible xor of two elements from the array.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= 'T' <= 10^3
1 <= 'L' <= 'R' <= 10^9

Time Limit: 1 sec

Sample Input 1 :

2
8 20
1 3

Sample Output 1 :

31
3

Explanation for Sample Input 1 :

For case 1:
The array looks like [8, 9, 10, ….., 18, 19, 20]. From all possible pairs (a, b), pair (15, 16) gives maximum value of xor, which is 15 ⊕ 16 = 31.

For Case 2:
Optimal pair is (2, 3), which gives 2 ⊕ 3 = 3.

Sample Input 2 :

2
4 10
4 7

Sample Output 2 :

15
3

Hint 1

Hint 2

Can you check for all possible pairs (a, b)?

Approaches (2)

Approach 1

Approach 2

Brute Force

Approach: Run two loops (nested) to find all possible pairs (a, b) such that (L <= a, b <= R) and calculate (a ⊕ b). Finally, return maximum xor value among all generated pairs.

Algorithm:

Initialize answer with 0, i.e., ans = 0.
Iterate a for loop, i = L to R.
- Iterate another for loop, j = i+1 to R.
  - Find xor value for current pair.
  - Maximize ‘ans’ with current xor value.
Return ‘ans’.

Time Complexity

O(N ^ 2), where ‘N’ is the number of elements in array ‘A’, i.e. (N = R - L + 1).

We are finding xor value for each possible pair in the given range. Hence overall time complexity becomes O(N ^ 2).

Space Complexity

O(1).

We are using only constant space. Hence overall space complexity is O(1).

(100% EXP penalty)

Maximize xor

Console