Description
You are given an array nums
consisting of non-negative integers. You are also given a queries
array, where queries[i] = [xi, mi]
.
The answer to the ith
query is the maximum bitwise XOR
value of xi
and any element of nums
that does not exceed mi
. In other words, the answer is max(nums[j] XOR xi)
for all j
such that nums[j] <= mi
. If all elements in nums
are larger than mi
, then the answer is -1
.
Return an integer array answer
where answer.length == queries.length
and answer[i]
is the answer to the ith
query.
Example 1:
Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]] Output: [3,3,7] Explanation: 1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3. 2) 1 XOR 2 = 3. 3) 5 XOR 2 = 7.
Example 2:
Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]] Output: [15,-1,5]
Constraints:
1 <= nums.length, queries.length <= 105
queries[i].length == 2
0 <= nums[j], xi, mi <= 109
Solution
Python3
class Solution:
def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
N = len(nums)
root = [None, None]
Q = sorted([(m, x, i) for i, (x, m) in enumerate(queries)])
nums.sort()
ans = [-1] * len(Q)
MAX_BIT = 32
def add(x):
curr = root
for k in range(MAX_BIT, -1, -1):
if x & (1 << k) > 0:
bit = 1
else:
bit = 0
if curr[bit] is None:
curr[bit] = [None, None]
curr = curr[bit]
def query(x):
curr = root
res = 0
for k in range(MAX_BIT, -1, -1):
if x & (1 << k) > 0:
bit = 1
else:
bit = 0
opp = 1 - bit
if curr is None: return -1
if curr[opp] is not None:
res += (1 << k)
curr = curr[opp]
else:
curr = curr[bit]
return res
index = 0
for m, x, qi in Q:
while index < N and nums[index] <= m:
add(nums[index])
index += 1
ans[qi] = query(x)
return ans