Scribd
Upload
12 views2 pages

Code 3

The document contains a C++ implementation of a Trie data structure to efficiently perform maximum XOR queries on an array of integers. It defines a TrieNode structure for storing binary representations and a Trie class for inserting numbers and querying maximum XOR values. The main function processes multiple queries by sorting the array and the queries, inserting eligible elements into the Trie, and calculating the results accordingly.

Uploaded by

iitiananmolgupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views2 pages

Code 3

The document contains a C++ implementation of a Trie data structure to efficiently perform maximum XOR queries on an array of integers. It defines a TrieNode structure for storing binary representations and a Trie class for inserting numbers and querying maximum XOR values. The main function processes multiple queries by sorting the array and the queries, inserting eligible elements into the Trie, and calculating the results accordingly.

Uploaded by

iitiananmolgupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <bits/stdc++.

h>
using namespace std;

// Trie Node to store binary representation of numbers


struct TrieNode {
TrieNode* links[2]; // 0 and 1 children

// Check if a child with given bit exists


bool contains(int bit) {
return links[bit] != NULL;
}

// Create a child node for the given bit


void put(int bit, TrieNode* node) {
links[bit] = node;
}

// Get the child node for the given bit


TrieNode* get(int bit) {
return links[bit];
}
};

// Trie to insert numbers and perform max XOR queries


class Trie {
TrieNode* root;
public:
Trie() {
root = new TrieNode(); // initialize root
}

// Insert a number into the Trie bit by bit


void insert(int num) {
TrieNode* node = root;
for (int i = 31; i >= 0; i--) { // 32-bit integers
int bit = (num >> i) & 1;
if (!node->contains(bit)) {
node->put(bit, new TrieNode());
}
node = node->get(bit);
}
}

// Get maximum XOR of given number with any number in Trie


int getMaxXOR(int num) {
TrieNode* node = root;
if (!node) return -1;

int maxNum = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;

// Prefer to take the opposite bit to maximize XOR


if (node->contains(1 - bit)) {
maxNum |= (1 << i); // set i-th bit in result
node = node->get(1 - bit);
} else if (node->contains(bit)) {
node = node->get(bit);
} else {
return -1; // Trie is empty
}
}
return maxNum;
}
};
// Struct to store each query with its original index
struct Query {
int xi; // value to XOR
int ai; // max allowed value in array
int idx; // original index of query
};

// Main function to handle multiple max XOR queries


vector<int> maximizeXor(vector<int>& arr, vector<vector<int>>& queries) {
vector<int> result(queries.size(), -1); // initialize result array

// Step 1: Sort the array


sort(arr.begin(), arr.end());

// Step 2: Convert queries to structured format and sort by ai


vector<Query> offlineQueries;
for (int i = 0; i < queries.size(); ++i) {
offlineQueries.push_back({queries[i][0], queries[i][1], i});
}
sort(offlineQueries.begin(), offlineQueries.end(), [](Query& a, Query& b) {
return a.ai < b.ai; // sort by ai to insert eligible elements
});

Trie trie;
int i = 0; // pointer for array

// Step 3: Process queries in sorted ai order


for (auto& q : offlineQueries) {
// Insert array elements ≤ ai into the Trie
while (i < arr.size() && arr[i] <= q.ai) {
trie.insert(arr[i]);
i++;
}

// If Trie is not empty, compute max XOR with xi


if (i > 0) {
result[q.idx] = trie.getMaxXOR(q.xi);
} else {
result[q.idx] = -1; // No element in array ≤ ai
}
}

return result;
}

// Driver code to test the function


int main() {
vector<int> arr = {0, 1, 2, 3, 4}; // Input array
vector<vector<int>> queries = {{3, 1}, {1, 3}, {5, 6}}; // {xi, ai}

vector<int> ans = maximizeXor(arr, queries);

// Output the answers to all queries


for (int x : ans) {
cout << x << " ";
}
cout << endl;

return 0;
}

You might also like