> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/1707.-maximum-xor-with-an-element-from-array.md).

# 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/)