Formatted question description: https://leetcode.ca/all/1707.html

1707. Maximum XOR With an Element From Array

Level

Hard

Description

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x_i, m_i].

The answer to the i-th query is the maximum bitwise XOR value of x_i and any element of nums that does not exceed m_i. In other words, the answer is max(nums[j] XOR x_i) for all j such that nums[j] <= m_i. If all elements in nums are larger than m_i, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i-th 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], x_i, m_i <= 10^9

Solution

Create a trie from the numbers in nums. Each node in the trie has two children that represent bits 0 and 1, respectively. For each number, create the trie from the highest bit to the lowest bit, where all the numbers have 32 bits. For each node in the trie, maintain the minimum number in nums that can reach the node.

Then for each query, obtain the values x and m, and use x to find the maximum possible xor result. If the last bit is met and the minimum value of the last bit is less than or equal to m, then calculate the xor value accordingly. Otherwise, the query result is -1.

Finally, return the query results.

Java

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        TrieNode root = new TrieNode();
        for (int num : nums) {
            TrieNode node = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (num & (1 << i)) == 0 ? 0 : 1;
                if (node.children[bit] == null)
                    node.children[bit] = new TrieNode();
                node = node.children[bit];
                node.min = Math.min(node.min, num);
            }
            node.isEnd = true;
        }
        int queriesCount = queries.length;
        int[] maxXors = new int[queriesCount];
        for (int i = 0; i < queriesCount; i++) {
            int xor = 0;
            int[] query = queries[i];
            int x = query[0], m = query[1];
            TrieNode node = root;
            boolean flag = true;
            for (int j = 31; j >= 0; j--) {
                int bit = (x & (1 << j)) == 0 ? 1 : 0;
                if (node.children[bit] != null && node.children[bit].min <= m) {
                    if (bit == 1)
                        xor ^= 1 << j;
                    node = node.children[bit];
                } else if (node.children[1 - bit] != null && node.children[1 - bit].min <= m) {
                    if (bit == 0)
                        xor ^= 1 << j;
                    node = node.children[1 - bit];
                } else {
                    flag = false;
                    break;
                }
            }
            if (node.isEnd && flag)
                maxXors[i] = xor ^ x;
            else
                maxXors[i] = -1;
        }
        return maxXors;
    }
}

class TrieNode {
    int min = Integer.MAX_VALUE;
    boolean isEnd;
    TrieNode[] children;

    public TrieNode() {
        children = new TrieNode[2];
        isEnd = false;
    }
}

All Problems

All Solutions