New update is available. Click here to update.
sidenav-btnClose
Topic list
Maximum XOR With an Element From Array
HARD
50 mins
48 upvotes
Tries
Bit Manipulation
Topics (Covered in this problem)
Problem solved
Skill meter
Tries
-
Bit Manipulation
-
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Trees
-
Graph
-
Dynamic Programming
-
Greedy
-
Arrays
-
Binary Search Trees
-
Heap
-

Maximum XOR With an Element From Array

Contributed by
Aditya Agarwal
Hard
Avg time to solve 50 mins
Success Rate 50 %
Share
48 upvotes

Problem Statement

You are given an array/list ‘ARR’ consisting of ‘N’ non-negative integers. You are also given a list ‘QUERIES’ consisting of ‘M’ queries, where the ‘i-th’ query is a list/array of two non-negative integers ‘Xi’, ‘Ai’, i.e ‘QUERIES[i]’ = [‘Xi’, ‘Ai’].

The answer to the ith query, i.e ‘QUERIES[i]’ is the maximum bitwise xor value of ‘Xi’ with any integer less than or equal to ‘Ai’ in ‘ARR’.

You should return an array/list consisting of ‘N’ integers where the ‘i-th’ integer is the answer of ‘QUERIES[i]’.

Note:

1. If all integers are greater than ‘Ai’ in array/list ‘ARR’  then the answer to this ith query will be -1.
Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1:
2
5 2
0 1 2 3 4
1 3
5 6
1 1
1
1 0  
Sample Output 1:
3 7
-1
Explanation of sample input 1:
In the first test case, the answer of query [1, 3] is 3 because 1^2 = 3 and 2 <= 3,  and the answer of query [5, 6] is 7 because  5 ^ 2 = 7 and 2 <= 6.

In the second test case, no element is less than or equal to 0 in the given array ‘ARR’.
Sample Input 2:
2
6 3
6 6 3 5 2 4
6 3
8 1
12 4 
5 2
0 0 0 0 0
1 0
1 1
Sample Output 2:
5 -1 15
1 1
Reset Code
Full screen
copy-code
Console