Maximum XOR Queries With an Element From Array

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

// Function to find the maximum XOR for each query
vector<int> maxXor(vector<int> &arr, vector<vector<int>> &queries){
    
    // Number of elements in the array
    int n = arr.size();  
    
    // Number of queries
    int q = queries.size();
    
    // Initialize the result vector with -1
    vector<int> result(q, -1);

    // Loop over each query
    for (int i = 0; i < q; i++){
        
        // Value to XOR with
        int xi = queries[i][0];
        
        // Maximum allowed value from arr
        int mi = queries[i][1];   
        
        // Track the maximum XOR for this query
        int maxXor = -1;    
        
        // Check all elements in arr
        for (int j = 0; j < n; j++) {
            
            // Only consider elements less than or equal to mi
            if (arr[j] <= mi){
                
                // Update maxXor if this XOR is greater than 
                // the current maximum
                maxXor = max(maxXor, arr[j] ^ xi);
            }
        }

        // Store the result for this query
        result[i] = maxXor;
    }

    // Return results for all queries
    return result;
}

int main(){
    
    vector<int> arr = {0, 1, 2, 3, 4};
    
    vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}};
    
    vector<int> ans = maxXor(arr, queries);
    
    // Output the results
    for(auto it: ans){
        cout << it << ' ';
    }

    return 0;
}

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

// Trie Node class
class node {
public:
    node *left;
    node *right;
};

// Trie class to insert numbers and find maximum XOR
class trie {
    node *root;

public:
    // Constructor to initialize the root
    trie() {
        root = new node();
    }

    // Insert a number into the Trie (bit by bit from MSB to LSB)
    void insert(int n) {
        node *temp = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (bit == 0) {
                if (temp->left == NULL)
                    temp->left = new node();
                temp = temp->left;
            } else {
                if (temp->right == NULL)
                    temp->right = new node();
                temp = temp->right;
            }
        }
    }

    // Helper function to find the maximum XOR value with a given number
    int xorHelper(int value) {
        int curr = 0;
        node *temp = root;

        for (int j = 31; j >= 0; j--) {
            int bit = (value >> j) & 1;

            // Prefer the opposite bit for maximizing XOR
            if (bit == 0) {
                if (temp->right != NULL) {
                    temp = temp->right;
                    curr += (1 << j); 
                } else {
                    temp = temp->left;
                }
            } else {
                if (temp->left != NULL) {
                    temp = temp->left;
                    curr += (1 << j); 
                } else {
                    temp = temp->right;
                }
            }
        }

        return curr;
    }
};

// Function to answer all max XOR queries
vector<int> maxXor(vector<int> &arr, vector<vector<int>> &queries) {
    int n = arr.size(), q = queries.size();
    vector<int> ans(q); // Result array
    vector<vector<int>> qry;
    
    // Sort array for efficient traversal
    sort(arr.begin(), arr.end()); 

    // Transform queries: [mi, xi, index] for sorting by mi
    for (int i = 0; i < q; i++) {
        qry.push_back({queries[i][1], queries[i][0], i});
    }

    // Sort queries by mi (max value constraint)
    sort(qry.begin(), qry.end());

    int j = 0;
    trie tree;

    // Process each query in increasing order of mi
    for (int i = 0; i < q; i++) {
        
        // Insert all array elements <= mi into the Trie
        while (j < arr.size() && arr[j] <= qry[i][0]) {
            tree.insert(arr[j++]);
        }

        // If no elements <= mi, answer is -1
        if (j == 0)
            ans[qry[i][2]] = -1;
        else
            // Get max XOR with xi using Trie
            ans[qry[i][2]] = tree.xorHelper(qry[i][1]);
    }

    return ans;
}

int main() {
    vector<int> arr = {0, 1, 2, 3, 4};

    // Sample queries: each query is {xi, mi}
    vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}};

    // Get answers for the queries
    vector<int> ans = maxXor(arr, queries);

    // Output the results
    for (auto it : ans) {
        cout << it << ' ';
    }

    return 0;
}