Problem Statement

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

Examples

Example 1:

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.

Example 2:

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.

Different Approaches

1️⃣ Brute Force Approach

Approach:

• For each query [xi, mi], iterate through all numbers in nums and check which numbers are ≤ mi.
• Compute xi XOR num for each valid number and keep track of the maximum XOR.
• If no valid numbers exist, return -1.

Code:

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> results;
        
        for (auto& query : queries) {
            int xi = query[0], mi = query[1];
            int max_xor = -1;

            for (int num : nums) {
                if (num <= mi) {
                    max_xor = max(max_xor, xi ^ num);
                }
            }

            results.push_back(max_xor);
        }

        return results;
    }
};

int main() {
    vector<int> nums = {0, 1, 2, 3, 4};
    vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}};
    
    Solution sol;
    vector<int> res = sol.maximizeXor(nums, queries);
    
    for (int val : res) cout << val << " ";
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(Q*N)
  • Iterating through nums for each query: O(Q × N)
  • Inefficient for large nums and queries.
• Space Complexity:O(1)

2️⃣ Tries + Sorting

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:

1. Build a Trie Node to hold binary bits (0 and 1), and add methods to insert numbers and find the maximum XOR value.
2. 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.
3. 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.
4. After all queries are processed, return the results. This method ensures we handle each query efficiently.

Code:

 #include <vector>
#include <algorithm>

using namespace std;

// Definition of a TrieNode
class TrieNode {
public:
    TrieNode* node[2]; // Pointers to child nodes representing bits 0 and 1

    // Constructor initializes both child pointers to nullptr
    TrieNode() {
        node[0] = nullptr;
        node[1] = nullptr;
    }
};

// Definition of the Trie data structure
class Trie {
public:
    TrieNode* root; // Root node of the Trie

    // Constructor initializes the root node
    Trie() {
        root = new TrieNode();
    }

    // Method to insert a number into the Trie
    void insert(int num) {
        TrieNode* currentNode = root;
        // Iterate over each bit from the 31st to the 0th (assuming 32-bit integers)
        for (int i = 31; i >= 0; i--) {
            // Extract the i-th bit of num
            int bit = (num >> i) & 1;
            // If the corresponding child node doesn't exist, create it
            if (currentNode->node[bit] == nullptr) {
                currentNode->node[bit] = new TrieNode();
            }
            // Move to the child node
            currentNode = currentNode->node[bit];
        }
    }

    // Method to find the maximum XOR of a given number with the numbers in the Trie
    int getMaxXOR(int num) {
        TrieNode* currentNode = root;
        int maxXOR = 0;
        // Iterate over each bit from the 31st to the 0th
        for (int i = 31; i >= 0; i--) {
            // Extract the i-th bit of num
            int bit = (num >> i) & 1;
            // Determine the opposite bit
            int oppositeBit = 1 - bit;
            // If the opposite bit exists in the Trie, it contributes to maximizing the XOR
            if (currentNode->node[oppositeBit] != nullptr) {
                maxXOR |= (1 << i); // Set the i-th bit of maxXOR
                currentNode = currentNode->node[oppositeBit];
            } else {
                // Otherwise, move to the node with the same bit
                currentNode = currentNode->node[bit];
            }
        }
        return maxXOR;
    }
};

// Solution class to handle the queries
class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        // Step 1: Sort the nums array
        sort(nums.begin(), nums.end());

        // Step 2: Restructure the queries to include their original indices
        vector<pair<int, pair<int, int>>> restructuredQueries;
        for (int i = 0; i < queries.size(); i++) {
            int xi = queries[i][0]; // The number to XOR with
            int mi = queries[i][1]; // The maximum allowable value in nums
            restructuredQueries.push_back({mi, {xi, i}});
        }

        // Step 3: Sort the restructured queries based on mi
        sort(restructuredQueries.begin(), restructuredQueries.end());

        vector<int> ans(queries.size(), -1); // Initialize answer vector with -1
        Trie trie; // Instantiate the Trie
        int index = 0; // Pointer for the nums array

        // Step 4: Process each query
        for (auto& query : restructuredQueries) {
            int mi = query.first;         // Maximum allowable value
            int xi = query.second.first;  // Number to XOR with
            int qIndex = query.second.second; // Original index of the query

            // Insert all numbers from nums that are <= mi into the Trie
            while (index < nums.size() && nums[index] <= mi) {
                trie.insert(nums[index]);
                index++;
            }

            // If the Trie is not empty, find the maximum XOR for xi
            if (index > 0) {
                ans[qIndex] = trie.getMaxXOR(xi);
            }
        }
        return ans;
    }
};

Complexity Analysis:

• Time Complexity:
  • Sorting the nums array:
    • It takes O(n log n) time.
  • Restructuring and Sorting Queries:
    • Assuming there are q queries, restructuring them takes O(q) time, and sorting them takes O(q log q) time.
  • Insertion into the Trie:
    • Each number is represented as a 32-bit integer, so inserting a number into the Trie takes O(32) = O(1) time.
    • Total insertion Time = O(n) * O(1) = O(n).
  • Finding Maximum XOR:
    • Traversing the Trie to compute the maximum XOR takes O(32) = O(1) time.
    • Total for All queries = O(q) * O(1) = O(q).
  • Overall Time Complexity:
    • O(n log n + q log q + n + q.
    • Simplifying it: O(n log n + q log q).
• Space Complexity:
  • Trie Storage: Each number requires up to 32 nodes in the worst case.
  • Total Space for Trie: O(n * 32) = O(n).
  • Auxiliary Space: Additional space is used for storing the answer and the restructured queries, both requiring O(q) space.
  • Overall Space complexity: O(q + n).