Maximum XOR With an Element From Array

Hard
0/120
Average time to solve is 50m
profile
Contributed by
105 upvotes
Asked in companies
AppleUberTata1mg

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, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two space-separated integers ‘N’ and ‘M’ representing the size of array/list ‘ARR’ and number of queries respectively.

The second line of each test case will contain ‘N’ space-separated integers representing array/list ‘ARR’.

The next ‘M’ line of each test case contains the description of ‘QUERIES’. The ‘i-th’ line of these ‘M’ lines consists of two space-separated integers ‘Xi’, ‘Ai’ as described in the problem statement.
Output Format: 
For each test case, print ‘M’ space-separated integer where the ‘i-th’ integer is the answer of the ‘i-th’ query.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 50
1 <= N, M <= 10000
0 <= ARR[i], Xi, Ai <= 10^9

Where ‘T’ is the number of test cases, 'N' is the size of ‘ARR’, ‘M’  is the number of queries, ‘ARR[i]’ is an element of array/list ‘ARR’ and ‘Xi’, ‘Ai’ are the integers in ‘QUERIES[i]’.  

Time limit: 1 sec
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
Hint

For each query try out all integers in the given array.

Approaches (3)
Brute Force

The basic idea is to iterate over the array ‘ARR’ for each query. For the ith query i.e ‘QUERIES[i]’, we iterate over ‘ARR’ and find the xor of ‘Xi’ with every integer in ‘ARR’ smaller or equal to ‘Ai’, If every integer in ‘ARR’ is greater than ‘Ai’, then the answer of this query is -1 otherwise, it is maximum xor value.

 

The steps are as follows:

  1. Create an integer array/list ‘RESULT’ of size ‘M’, and initially fill it with -1.
  2. Run a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ do the following -:
    1. Run a loop where ‘j’ ranges from 0 to ‘N’-1 and do following -:
      1. If ARR[j] <= QUERIES[i][1] then do ‘RESULT[i]’:= max('RESULT[i]', ‘ARR[j]’ XOR ‘QUERIES[i][0]’) .  (Note, QUERIES[i][0] is Xi, and QUERIES[i][1] is Ai).
  3. Return ‘RESULT’.
Time Complexity

O(N*M), where 'N' is the size of ‘ARR’, and ‘M’  is the number of queries.

 

There are ‘M’ queries, and for each query, we iterate over an array ‘ARR’ of size ‘N’ and find xor with integers in it. Thus, the overall time complexity will be O(N*M).  :

Space Complexity

O(1)

 

We are using constant extra space here.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Maximum XOR With an Element From Array
Full screen
Console