Maximum XOR With an Element From Array

1. Initialize an answer array of the same size as queries.
2. For each query [xi, mi] in queries: a. Initialize max_xor = -1. b. Iterate through each number num in nums. c. If num <= mi: i. Calculate current_xor = xi XOR num. ii. Update max_xor = max(max_xor, current_xor). d. Store max_xor in the answer array for the current query.
3. Return the answer array.

We initialize an answer array to store the results for each query. We loop through each query [x_i, m_i] from the queries array. For each query, we initialize a variable max_xor to -1. This variable will keep track of the maximum XOR value found so far for the current query. We then iterate through every number num in the nums array. Inside this inner loop, we check if num <= m_i. If the condition is met, we calculate the bitwise XOR of x_i and num. We then update max_xor to be the maximum of its current value and the newly calculated XOR value. After iterating through all numbers in nums, the value of max_xor is the answer for the current query. If no number satisfied the condition, max_xor remains -1. We store this result in our answer array. Finally, after processing all queries, we return the answer array.

1class Solution {2    public int[] maximizeXor(int[] nums, int[][] queries) {3        int n = queries.length;4        int[] answer = new int[n];5        for (int i = 0; i < n; i++) {6            int x = queries[i][0];7            int m = queries[i][1];8            int maxVal = -1;9            for (int num : nums) {10                if (num <= m) {11                    maxVal = Math.max(maxVal, x ^ num);12                }13            }14            answer[i] = maxVal;15        }16        return answer;17    }18}

1. Create an indexedQueries array where each element is [x, m, original_index].
2. Sort the nums array in ascending order.
3. Sort the indexedQueries array based on the m value in ascending order.
4. Initialize an empty Trie, an answer array of size queries.length, and a pointer numsIndex = 0.
5. For each [x, m, originalIndex] in sortedQueries:
6. While numsIndex < nums.length and nums[numsIndex] <= m:
7. Insert `nums[numsIndex]` into the Trie.
8. Increment `numsIndex`.
9. If numsIndex == 0 (Trie is empty):
10. Set answer[originalIndex] = -1.
11. Else:
12. Query the Trie with x to find the maximum XOR value.
13. Set answer[originalIndex] to this maximum value.
14. Return answer.

The main idea is to answer queries "offline". Instead of answering them in the given order, we reorder them to process them more efficiently. We sort the nums array in ascending order. We also sort the queries array based on their m_i values. Since we need to return the answers in the original order, we augment the queries with their original indices before sorting, e.g., [x_i, m_i, original_index]. We use a Trie (Prefix Tree) to store the binary representations of numbers. Each node in the Trie has two children, representing bits 0 and 1. We iterate through the sorted queries. For each query [x, m, original_idx], we first add all numbers from the sorted nums array that are less than or equal to m into the Trie. Since both nums and queries (by m) are sorted, we can do this with a single pointer on the nums array, which advances monotonically. After updating the Trie with all numbers <= m, we query the Trie with x to find the number that gives the maximum XOR value. To do this, we traverse the Trie from the most significant bit to the least significant. At each bit position, we try to take a path that is opposite to the corresponding bit of x to maximize the XOR result. If such a path doesn't exist, we take the only available path. If the Trie is empty when we process a query (meaning no number in nums is <= m), the answer is -1. The result for each query is stored in an answer array at its original index. Finally, we return the fully populated answer array.

1class TrieNode {2    TrieNode[] children = new TrieNode[2];3}4 5class Trie {6    TrieNode root = new TrieNode();7    private static final int MAX_BIT = 30;8 9    public void insert(int num) {10        TrieNode curr = root;11        for (int i = MAX_BIT; i >= 0; i--) {12            int bit = (num >> i) & 1;13            if (curr.children[bit] == null) {14                curr.children[bit] = new TrieNode();15            }16            curr = curr.children[bit];17        }18    }19 20    public int getMaxXor(int num) {21        TrieNode curr = root;22        int maxXor = 0;23        for (int i = MAX_BIT; i >= 0; i--) {24            int bit = (num >> i) & 1;25            int oppositeBit = 1 - bit;26            if (curr.children[oppositeBit] != null) {27                maxXor |= (1 << i);28                curr = curr.children[oppositeBit];29            } else {30                curr = curr.children[bit];31            }32        }33        return maxXor;34    }35}36 37class Solution {38    public int[] maximizeXor(int[] nums, int[][] queries) {39        Arrays.sort(nums);40        int numQueries = queries.length;41        int[][] indexedQueries = new int[numQueries][3];42        for (int i = 0; i < numQueries; i++) {43            indexedQueries[i][0] = queries[i][0];44            indexedQueries[i][1] = queries[i][1];45            indexedQueries[i][2] = i;46        }47 48        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(a[1], b[1]));49 50        int[] ans = new int[numQueries];51        Trie trie = new Trie();52        int numsIndex = 0;53 54        for (int[] query : indexedQueries) {55            int x = query[0];56            int m = query[1];57            int originalIndex = query[2];58 59            while (numsIndex < nums.length && nums[numsIndex] <= m) {60                trie.insert(nums[numsIndex]);61                numsIndex++;62            }63 64            if (numsIndex == 0) {65                ans[originalIndex] = -1;66            } else {67                ans[originalIndex] = trie.getMaxXor(x);68            }69        }70        return ans;71    }72}