Sponsored
Sponsored
This approach involves iterating over all possible pairs of numbers in the array and calculating their XOR. We keep track of the maximum XOR value encountered during these iterations.
Though straightforward, this method is not efficient for large arrays, as it involves checking each pair of numbers.
Time Complexity: O(n^2), where n is the number of elements in the array, because it checks every pair.
Space Complexity: O(1), as it uses only a constant amount of space.
1function findMaximumXOR(nums) {
2 let maxXor = 0;
3 for (let i = 0; i < nums.length; i++) {
4 for (let j = i; j < nums.length; j++) {
5 maxXor = Math.max(maxXor, nums[i] ^ nums[j]);
6 }
7 }
8 return maxXor;
9}
10
11const nums = [3, 10, 5, 25, 2, 8];
12console.log("Maximum XOR:", findMaximumXOR(nums));The JavaScript function findMaximumXOR evaluates all unique pairs within the array. It uses a nested loop to compute the XOR for each combination and updates the maximum XOR value accordingly.
This approach makes use of a Trie data structure to efficiently maximize the XOR computation. By examining the binary representation of numbers, we can leverage the Trie to only explore branches that potentially maximize the XOR result.
The Trie helps in finding complementary patterns (bits) efficiently by using bit manipulation and path traversal.
Time Complexity: O(n * W), where n is the number of elements and W is the number of bits in the maximum number.
Space Complexity: O(n * W), for storing the Trie.
class TrieNode {
public TrieNode[] children = new TrieNode[2];
}
public class Solution {
private void Insert(TrieNode root, int num) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
}
}
public int FindMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
int maxXor = 0;
foreach (int num in nums) {
TrieNode node = root;
TrieNode xorNode = root;
int currentXor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.children[bit] == null) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
int toggledBit = 1 - bit;
if (xorNode.children[toggledBit] != null) {
currentXor |= (1 << i);
xorNode = xorNode.children[toggledBit];
} else {
xorNode = xorNode.children[bit];
}
}
maxXor = Math.Max(maxXor, currentXor);
Insert(root, num);
}
return maxXor;
}
public static void Main() {
Solution solution = new Solution();
int[] nums = {3, 10, 5, 25, 2, 8};
Console.WriteLine("Maximum XOR: " + solution.FindMaximumXOR(nums));
}
}In this C# implementation, numbers are inserted into a Trie, and we compute XOR during insertion by exploiting the search path that maximizes XOR by choosing alternate bit paths.