Maximum XOR With an Element From Array

Problem

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x<sub>i</sub>, m<sub>i</sub>]. (link)

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

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i<sup>th</sup> 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]

Solution

• We have several queries, each with two elements: X and M.

• For each query, find the maximum XOR value of X with elements from the array that are less than or equal to M.

• Optimized Method:

  • Insert elements into the trie only up to the maximum value allowed by the query.

  • Insert elements in ascending order to manage the trie easily and find the maximum XOR.

• Convert online queries into offline queries:

  • Identify the offline query with the smallest elements that can be inserted.

  • Sort the queries.

  • Start inserting elements up to M, beginning with the smallest values, and gradually increase the maximum value sequentially..

Note: An online query means we process each query one after the other in sequence. In contrast, an offline query allows us to process any query first. Offline queries store the index of the online query they belong to.

Time - O(QlogQ) + O(Q) + O(N)

class Node {
    Node[] nodeArr;

    Node(){
        nodeArr = new Node[2];
    }

    public void put(int bit, Node node){
        nodeArr[bit] = node;
    }

    public Node get(int bit){
        return nodeArr[bit];
    }

    public boolean containsKey(int bit){
        return nodeArr[bit] != null;
    }
}

class Trie {
    Node root;

    Trie(){
        root = new Node();
    }

    public void insert(int num){
        Node node = root;
        for(int i=31; i>=0; i--){
            int bit = num>>i & 1;
            if(!node.containsKey(bit)){
                node.put(bit, new Node());
            }
            node = node.get(bit);
        }
    }

    public int getMax(int x){
        Node node = root;
        int ans = 0;
        for(int i=31; i>=0; i--){
            int bit = x>>i & 1;
            int oppBit = 1 - bit;
            if(node.containsKey(oppBit)){
                ans = ans | (1<<i);
                node = node.get(oppBit);
            }
            else{
                node = node.get(bit);
            }
        }
        return ans;
    }
}

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {

        Arrays.sort(nums);

        List<List<Integer>> offlineQueries = new ArrayList<>();

        for(int i=0; i<queries.length; i++){
            int x = queries[i][0];
            int m = queries[i][1];
            offlineQueries.add(List.of(x, m, i));
        }

        // sort based on m
        offlineQueries.sort(Comparator.comparingInt(list -> list.get(1)));

        // insert into trie
        Trie trie = new Trie();
        int[] ans = new int[queries.length];
        int index = 0;
        for(List<Integer> offQuery : offlineQueries) {
            int x = offQuery.get(0);
            int m = offQuery.get(1);
            int i = offQuery.get(2);

            while(index<nums.length && nums[index]<=m){
                trie.insert(nums[index]);
                index+=1;
            }
            // if no number present in trie
            ans[i] = index==0 ? -1 : trie.getMax(x);
        }

        return ans;
    }
}