Maximum Xor with an element from an array

Tries Problems Hard

Given an array nums consisting of non-negative integers and 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.

Examples:

Input : nums = [4, 9, 2, 5, 0, 1] , queries = [ [3, 0], [3, 10], [7, 5], [7,9] ]

Output : [3, 10, 7, 14]

Explanation : 1st query : x = 3, m = 0. There are only one numbers less than equal to m i.e 0. 0 XOR 3 = 3. The answer is 3.

2nd query : x = 3, m = 10. The maximum XOR is 3 XOR 9 = 10.

3rd query : x = 7, m = 5. The maximum XOR is 7 XOR 0 = 7.

4th query : x = 7, m = 9. The maximum XOR is 7 XOR 9 = 14.

Input : nums = [0, 1, 2, 3, 4] , queries = [ [3, 1], [1, 3], [5, 6] ]

Output : [3, 3, 7]

Explanation : 1st query : x = 3, m = 1. There are only two numbers less than equal to m i.e 0 , 1. 0 XOR 3 = 3, 1 XOR 3 = 2. The larger value is 3.

2nd query : x = 1, m = 3. The maximum XOR is 1 XOR 2 = 3

3rd query : x = 5, m = 6. The maximum XOR is 5 XOR 2 = 7.

Input : nums = [5, 2, 4, 6, 6, 3] , queries = [ [12, 4], [8, 1], [6, 3] ]

Constraints

1 <= nums.length , queries.length <= 10⁵
queries[i].length == 2
0 <= nums[i] , x_i , m_i <= 10⁹

Hints

"Sort nums to enable efficient constraint handling (≤ mi). Use a Trie to store valid numbers dynamically while processing queries in increasing order of mi."
"For each query [xi, mi], find the best possible XOR using the Trie. Traverse the Trie to maximize the XOR value bit-by-bit, preferring the opposite bits."

Company Tags

Broadcom Philips Healthcare Flipkart Goldman Sachs Alibaba Dropbox Docker Boston Consulting Group KPMG Rakuten Qualcomm Intel Byju's Twilio Texas Instruments GE Healthcare Salesforce Freshworks Ubisoft HCL Technologies Ernst & Young Wayfair Micron Technology JPMorgan Chase Square Google Microsoft Amazon Meta Apple Netflix Adobe

Intuition

We can efficiently solve this problem by using a Trie data structure, where each node represents a bit and paths from the root to the leaves represent binary numbers. The aim is to maximize the XOR value between a given number and any number in the array that is less than or equal to a specified limit. By incrementally inserting numbers into the Trie up to the required value for each query, unnecessary operations are minimized. This approach allows for efficiently finding the maximum XOR for each query by traversing the Trie and selecting opposite bits whenever possible, ensuring the highest possible XOR result. If no numbers are less than or equal to the specified limit, the result is -1.

Approach

Build a Trie Node to hold binary bits (0 and 1), and add methods to insert numbers and find the maximum XOR value.
Set up a list to store query results, and sort the numbers and queries by their limits. This way, we only insert necessary numbers into the Trie.
Go through the sorted numbers and queries. For each query, add numbers to the Trie up to the query's limit and use the Trie to find the highest XOR value for the query.
After all queries are processed, return the results. This method ensures we handle each query efficiently.

Dry Run

For detailed dry run watch the video.

Solution

#include <bits/stdc++.h>
using namespace std;

// Node Structure for Trie
struct Node {
    Node *links[2];

  
    bool containsKey(int ind) {
        return (links[ind] != NULL);
    }

  
    Node* get(int ind) {
        return links[ind];
    }

    void put(int ind, Node* node) {
        links[ind] = node;
    }
};

// Definition for Trie data
class Trie {
private:
    Node* root;

public:
    // Constructor 
    Trie() {
        root = new Node();
    }

    // Function to insert 
    void insert(int num) {
        // Start traversal
        Node* node = root;

       /* Traverse each bit of the number 
       from the most significant bit to the 
       least significant bit*/
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;

            /*If the current node doesn't have 
            a child node at the current bit, 
            create one*/
            if (!node->containsKey(bit)) {
                node->put(bit, new Node());
            }

           /* Move to the child node
            corresponding to the 
            current bit*/
            node = node->get(bit);
        }
    }

    // Function to find maximum XOR
    int findMax(int num) {
        Node* node = root;

        int maxNum = 0;

        /*Traverse each bit of the number from 
        the most significant bit to the least 
        significant bit extract the i-th 
        bit of the number.
        If there exists a different bit 
        in the trie at the current 
        position, choose it to maximize XOR*/
        for (int i = 31; i >= 0; i--) {
            
            int bit = (num >> i) & 1;

            
            if (node->containsKey(!bit)) {
                maxNum = maxNum | (1 << i);
                node = node->get(!bit);
            } else {
                node = node->get(bit);
            }
        }

        // Return maximum XOR value
        return maxNum;
    }
};

// Solution class to handle queries
class Solution {
public:
    // Function to handle the maximize XOR queries
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        // Initialize vector to store results of queries
        vector<int> ans(queries.size(), 0);

        // Vector to store offline queries
        vector<pair<int, pair<int, int>>> offlineQueries;

        // Sort the array of numbers
        sort(nums.begin(), nums.end());

        // Convert queries to offline queries and store them in a vector
        int index = 0;
        for (auto &it : queries) {
            offlineQueries.push_back({it[1], {it[0], index++}});
        }

        // Sort queries based on their end points
        sort(offlineQueries.begin(), offlineQueries.end());
        int i = 0;
        int n = nums.size();

        Trie trie;

        // Process each query
        for (auto &it : offlineQueries) {
            // Insert numbers 
            while (i < n && nums[i] <= it.first) {
                trie.insert(nums[i]);
                i++;
            }

            /*If there are numbers inserted into the trie, 
            find the maximum XOR value for the query range*/
            if (i != 0)
                ans[it.second.second] = trie.findMax(it.second.first);
            else
                ans[it.second.second] = -1;
        }

        // Return results
        return ans;
    }
};

int main() {
    // Create instance of Solution class
    Solution sol;

    // Input array of numbers
    vector<int> nums = {0, 1, 2, 3, 4};

    // Queries in the form of [x, m]
    vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}};

    // Get the results of the maximize XOR queries
    vector<int> result = sol.maximizeXor(nums, queries);

    // Output the results
    cout << "Result of Max XOR Queries:" << endl;
    for (int i = 0; i < result.size(); ++i) {
        cout << "Query " << i+1 << ": " << result[i] << endl;
    }

    return 0;
}
import java.util.*;

// Node Structure for Trie
class Node {
    Node[] links = new Node[2];

  
    boolean containsKey(int ind) {
        return links[ind] != null;
    }

  
    Node get(int ind) {
        return links[ind];
    }

    void put(int ind, Node node) {
        links[ind] = node;
    }
}

// Definition for Trie data structure
class Trie {
    private Node root;

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

    // Function to insert a number into the trie
    void insert(int num) {
        // Start traversal
        Node node = root;

        /* Traverse each bit of the number 
           from the most significant bit to the 
           least significant bit */
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;

            /* If the current node doesn't have 
               a child node at the current bit, 
               create one */
            if (!node.containsKey(bit)) {
                node.put(bit, new Node());
            }

            /* Move to the child node
               corresponding to the 
               current bit */
            node = node.get(bit);
        }
    }

    // Function to find maximum XOR
    int findMax(int num) {
        Node node = root;
        int maxNum = 0;

        /* Traverse each bit of the number from 
           the most significant bit to the least 
           significant bit extract the i-th 
           bit of the number.
           If there exists a different bit 
           in the trie at the current 
           position, choose it to maximize XOR */
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;

            if (node.containsKey(1 - bit)) {
                maxNum = maxNum | (1 << i);
                node = node.get(1 - bit);
            } else {
                node = node.get(bit);
            }
        }

        // Return maximum XOR value
        return maxNum;
    }
}

// Solution class to handle queries
class Solution {
    // Function to handle the maximize XOR queries
    public int[] maximizeXor(int[] nums, int[][] queries) {
        // Initialize array to store results of queries
        int[] ans = new int[queries.length];

        // List to store offline queries
        List<int[]> offlineQueries = new ArrayList<>();

        // Sort the array of numbers
        Arrays.sort(nums);

        // Convert queries to offline queries and store them in a list
        for (int i = 0; i < queries.length; i++) {
            offlineQueries.add(new int[]{queries[i][1], queries[i][0], i});
        }

        // Sort queries based on their end points
        offlineQueries.sort(Comparator.comparingInt(a -> a[0]));

        int i = 0;
        Trie trie = new Trie();

        // Process each query
        for (int[] query : offlineQueries) {
            // Insert numbers 
            while (i < nums.length && nums[i] <= query[0]) {
                trie.insert(nums[i]);
                i++;
            }

            /* If there are numbers inserted into the trie, 
               find the maximum XOR value for the query range */
            if (i != 0)
                ans[query[2]] = trie.findMax(query[1]);
            else
                ans[query[2]] = -1;
        }

        // Return results
        return ans;
    }

    public static void main(String[] args) {
        // Create instance of Solution class
        Solution sol = new Solution();

        // Input array of numbers
        int[] nums = {0, 1, 2, 3, 4};

        // Queries in the form of [x, m]
        int[][] queries = {{3, 1}, {1, 3}, {5, 6}};

        // Get the results of the maximize XOR queries
        int[] result = sol.maximizeXor(nums, queries);

        // Output the results
        System.out.println("Result of Max XOR Queries:");
        for (int i = 0; i < result.length; ++i) {
            System.out.println("Query " + (i + 1) + ": " + result[i]);
        }
    }
}
# Node Structure for Trie
class Node:
    def __init__(self):
        # Initialize child links (0 and 1)
        self.links = [None, None]

    # Check if a child node exists at a given index (0 or 1)
    def contains_key(self, ind):
        return self.links[ind] is not None

    # Get the child node at a given index (0 or 1)
    def get(self, ind):
        return self.links[ind]

    # Set the child node at a given index (0 or 1)
    def put(self, ind, node):
        self.links[ind] = node

# Definition for Trie data structure
class Trie:
    def __init__(self):
        # Initialize root node
        self.root = Node()

    # Function to insert a number into the trie
    def insert(self, num):
        # Start traversal
        node = self.root

        # Traverse each bit of the number
        for i in range(31, -1, -1):
            bit = (num >> i) & 1

            # If the current node doesn't have a child node at the current bit, create one
            if not node.contains_key(bit):
                node.put(bit, Node())

            # Move to the child node corresponding to the current bit
            node = node.get(bit)

    # Function to find the maximum XOR value achievable with a given number
    def find_max(self, num):
        node = self.root
        max_num = 0

        # Traverse each bit of the number
        for i in range(31, -1, -1):
            bit = (num >> i) & 1

            # If there exists a different bit in the trie at the current position, choose it to maximize XOR
            if node.contains_key(1 - bit):
                max_num = max_num | (1 << i)
                node = node.get(1 - bit)
            else:
                node = node.get(bit)

        # Return the maximum XOR value
        return max_num

# Solution class to handle queries
class Solution:
    # Function to handle the maximize XOR queries
    def maximizeXor(self, nums, queries):
        # Initialize list to store results of queries
        ans = [0] * len(queries)

        # List to store offline queries
        offline_queries = []

        # Sort the array of numbers
        nums.sort()

        # Convert queries to offline queries and store them in a list
        for index, query in enumerate(queries):
            offline_queries.append((query[1], query[0], index))

        # Sort queries based on their end points
        offline_queries.sort()

        i = 0
        trie = Trie()

        # Process each query
        for m, x, query_index in offline_queries:
            # Insert numbers into the trie until the current query's end point
            while i < len(nums) and nums[i] <= m:
                trie.insert(nums[i])
                i += 1

            # If there are numbers inserted into the trie, find the maximum XOR value for the query range
            if i != 0:
                ans[query_index] = trie.find_max(x)
            else:
                ans[query_index] = -1

        # Return results
        return ans

# Main function to test the Solution class
if __name__ == "__main__":
    # Create instance of Solution class
    sol = Solution()

    # Input array of numbers
    nums = [0, 1, 2, 3, 4]

    # Queries in the form of [x, m]
    queries = [[3, 1], [1, 3], [5, 6]]

    # Get the results of the maximize XOR queries
    result = sol.maximizeXor(nums, queries)

    # Output the results
    print("Result of Max XOR Queries:")
    for i in range(len(result)):
        print(f"Query {i + 1}: {result[i]}")
// Node Structure for Trie
class Node {
    constructor() {
        this.links = [null, null];
    }

    containsKey(ind) {
        return this.links[ind] !== null;
    }

    get(ind) {
        return this.links[ind];
    }

    put(ind, node) {
        this.links[ind] = node;
    }
}

// Definition for Trie data structure
class Trie {
    constructor() {
        // Initialize root node
        this.root = new Node();
    }

    // Function to insert a number into the trie
    insert(num) {
        // Start traversal
        let node = this.root;

        /* Traverse each bit of the number 
           from the most significant bit to the 
           least significant bit */
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;

            /* If the current node doesn't have 
               a child node at the current bit, 
               create one */
            if (!node.containsKey(bit)) {
                node.put(bit, new Node());
            }

            /* Move to the child node
               corresponding to the 
               current bit */
            node = node.get(bit);
        }
    }

    // Function to find maximum XOR
    findMax(num) {
        let node = this.root;
        let maxNum = 0;

        /* Traverse each bit of the number from 
           the most significant bit to the least 
           significant bit extract the i-th 
           bit of the number.
           If there exists a different bit 
           in the trie at the current 
           position, choose it to maximize XOR */
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;

            if (node.containsKey(1 - bit)) {
                maxNum = maxNum | (1 << i);
                node = node.get(1 - bit);
            } else {
                node = node.get(bit);
            }
        }

        // Return maximum XOR value
        return maxNum;
    }
}

// Solution class to handle queries
class Solution {
    // Function to handle the maximize XOR queries
    maximizeXor(nums, queries) {
        // Initialize array to store results of queries
        const ans = new Array(queries.length).fill(0);

        // Array to store offline queries
        const offlineQueries = [];

        // Sort the array of numbers
        nums.sort((a, b) => a - b);

        // Convert queries to offline queries and store them in an array
        queries.forEach((query, index) => {
            offlineQueries.push([query[1], query[0], index]);
        });

        // Sort queries based on their end points
        offlineQueries.sort((a, b) => a[0] - b[0]);

        let i = 0;
        const trie = new Trie();

        // Process each query
        offlineQueries.forEach(query => {
            // Insert numbers 
            while (i < nums.length && nums[i] <= query[0]) {
                trie.insert(nums[i]);
                i++;
            }

            /* If there are numbers inserted into the trie, 
               find the maximum XOR value for the query range */
            if (i !== 0) {
                ans[query[2]] = trie.findMax(query[1]);
            } else {
                ans[query[2]] = -1;
            }
        });

        // Return results
        return ans;
    }
}

// Main function to test the Solution class
const main = () => {
    // Create instance of Solution class
    const sol = new Solution();

    // Input array of numbers
    const nums = [0, 1, 2, 3, 4];

    // Queries in the form of [x, m]
    const queries = [[3, 1], [1, 3], [5, 6]];

    // Get the results of the maximize XOR queries
    const result = sol.maximizeXor(nums, queries);

    // Output the results
    console.log("Result of Max XOR Queries:");
    result.forEach((res, i) => {
        console.log(`Query ${i + 1}: ${res}`);
    });
};

// Call the main function
main();

Complexity Analysis

Time Complexity: O(32N + Q(logQ) + 32Q) where N is the size of the input array and Q is the number of queries. The time complexity includes inserting N numbers into the Trie, each taking O(32) operations due to the 32-bit integer representation, resulting in O(32N). Sorting the Q queries takes O(Q(logQ)) time. Processing each query involves traversing the 32-bit Trie, resulting in O(32Q). Space Complexity: O(32N + Q) where N is the size of the input array and Q is the number of queries. The space complexity accounts for storing N numbers in the Trie (32N) and the storage needed for the Q queries.

Code

Problem List

Maximum Xor with an element from an array

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts