# 1707. Maximum XOR With an Element From Array

## LeetCode [1707. Maximum XOR With an Element From Array](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### 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 <= 10^5`
* `queries[i].length == 2`
* `0 <= nums[j], xi, mi <= 10^9`

### Tags

Bit Manipulation, Trie

### Solution

For a solution with less complexity, refer to Reference 1.

If there is no restriction `mi` for each query, we can obtain the query result by find a number `y` in `nums`, who shares different bits with `xi` as much as possible. To find such `y` efficiently, we can build a Trie tree. To take `mi` into consideration, we can sort both `nums` and `queries` first, then for each query, insert elements in nums one by one until `nums[j] > mi`. After inserting, if the trie tree is empty, we assign -1 to the result according to the requirement; otherwise we start to find such `y` we want.

### Complexity

* Time complexity: $$O(NlogN+QlogQ+(N+Q)⋅L)$$
* Space complexity: $$O(Q+N⋅L)$$

### Code

```go
const L = 30 // nums[i] <= 10^9

func maximizeXor(nums []int, queries [][]int) []int {
	ans, t, j := make([]int, len(queries)), &trie{}, 0
	sort.Ints(nums)
	for i := range queries {
		queries[i] = append(queries[i], i)
	}
	sort.Slice(queries, func(i, j int) bool {
		return queries[i][1] < queries[j][1]
	})
	for _, query := range queries {
		x, m, qIdx := query[0], query[1], query[2]
		for ; j < len(nums) && nums[j] <= m; j++ {
			t.insert(nums[j])
		}
		if j == 0 { // trie is empty
			ans[qIdx] = -1
		} else {
			ans[qIdx] = t.getMaxXor(x)
		}
	}
	return ans
}

type trie struct {
	children [2]*trie
}

func (t *trie) insert(num int) {
	p := t
	for i := L - 1; i >= 0; i-- {
		bit := num >> i & 1
		if p.children[bit] == nil {
			p.children[bit] = &trie{}
		}
		p = p.children[bit]
	}
}

func (t *trie) getMaxXor(num int) (ans int) {
	p := t
	for i := L - 1; i >= 0; i-- {
		bit := num >> i & 1
		if p.children[bit^1] != nil {
			ans |= 1 << i
			bit ^= 1
		}
		p = p.children[bit]
	}
	return
}
```

## Reference

1. [与数组中元素的最大异或值](https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/solution/yu-shu-zu-zhong-yuan-su-de-zui-da-yi-huo-7erc/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/1707.-maximum-xor-with-an-element-from-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.