LeetCode 3277: Maximum XOR Score Subarray Queries
Problem Description
Explanation:
To solve this problem efficiently, we can use the concept of Trie data structure along with bitwise manipulation. We will iterate through the given queries and build a Trie structure representing the binary representation of the numbers in the array. Then, for each query, we will traverse the Trie to find the maximum XOR score.
Algorithm:
- Implement a TrieNode class to represent a node in the Trie.
- Implement a Trie class to build the Trie structure from the binary representations of the numbers in the array.
- For each query [li, ri]:
- Traverse the Trie starting from the most significant bit.
- At each step, choose the maximum XOR path to maximize the final XOR score.
- Repeat this process for all queries and store the results in the answer array.
Time Complexity:
- Building the Trie structure: O(n * 32) ~ O(n) where n is the number of elements in the array.
- Processing each query: O(32) ~ O(1) since we are dealing with bits.
- Total time complexity: O(n + q) where q is the number of queries.
Space Complexity:
- Trie structure: O(n * 32) ~ O(n) to store the binary representation of each number.
- Additional space for storing the answer array and other variables.
- Total space complexity: O(n).
:
Solutions
class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(int num) {
TrieNode curr = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null) {
curr.children[bit] = new TrieNode();
}
curr = curr.children[bit];
}
}
public int findMaxXOR(int num) {
TrieNode curr = root;
int maxXOR = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[1 - bit] != null) {
maxXOR |= (1 << i);
curr = curr.children[1 - bit];
} else {
curr = curr.children[bit];
}
}
return maxXOR;
}
}
public int[] maximizeXor(int[] nums, int[][] queries) {
Trie trie = new Trie();
for (int num : nums) {
trie.insert(num);
}
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
result[i] = trie.findMaxXOR(queries[i][1]) ;
}
return result;
}Loading editor...