Maximum XOR of Two Numbers in an Array
Maximum XOR of Two Numbers in an Array:
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Example 1:
Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127
Constraints:
1 <= nums.length <= 2 * 10^50 <= nums[i] <= 2^31 - 1
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
class Solution {
class Trie {
private class TrieNode{
TrieNode[] children;
public TrieNode(){
children = new TrieNode[2];
}
}
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(int num) {
TrieNode iter = root;
for(int i = 31 ; i >= 0; --i){
int bit = (num >> i) & 1;
if(iter.children[bit] == null){
iter.children[bit] = new TrieNode();
}
iter = iter.children[bit];
}
}
public int searchForMostDifferent(int num){
TrieNode iter = root;
int xorDiff = 0;
for(int i = 31 ; i >= 0; --i){
int bit = ((num >> i) & 1) ^ 1;
if(iter.children[bit] != null){
iter = iter.children[bit];
xorDiff |= (1 << i);
}else{
iter = iter.children[bit ^ 1];
}
}
return xorDiff;
}
}
public int findMaximumXOR(int[] nums) {
int maxDifference = 0;
Trie trie = new Trie();
for(int num: nums){
trie.insert(num);
}
for(int num: nums){
maxDifference = Math.max(maxDifference, trie.searchForMostDifferent(num));
}
return maxDifference;
}
}
/**
* @param {number[]} nums
* @return {number}
*/
var findMaximumXOR = function (nums) {
let maxDifference = 0;
const trie = new Trie();
for (const num of nums) {
trie.insert(num);
}
for (const num of nums) {
maxDifference = Math.max(maxDifference, trie.searchForMostDifferent(num));
}
return maxDifference;
};
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(num) {
let iter = this.root;
for (let i = 31; i >= 0; --i) {
const bit = (num >> i) & 1;
if (!iter.children[bit]) {
iter.children[bit] = new TrieNode();
}
iter = iter.children[bit];
}
}
searchForMostDifferent(num) {
let iter = this.root;
let xorDiff = 0;
for (let i = 31; i >= 0; --i) {
const bit = ((num >> i) & 1) ^ 1;
if (iter.children[bit]) {
iter = iter.children[bit];
xorDiff |= 1 << i;
} else {
iter = iter.children[bit ^ 1];
}
}
return xorDiff;
}
}
class TrieNode {
constructor() {
this.children = Array(2).fill(null);
}
}
class Solution:
class Trie:
class TrieNode:
def __init__(self):
self.children = [None] * 2
def __init__(self):
self.root = self.TrieNode()
def insert(self, num):
iter = self.root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if not iter.children[bit]:
iter.children[bit] = self.TrieNode()
iter = iter.children[bit]
def searchForMostDifferent(self, num):
iter = self.root
xorDiff = 0
for i in range(31, -1, -1):
bit = ((num >> i) & 1) ^ 1
if iter.children[bit]:
iter = iter.children[bit]
xorDiff |= 1 << i
else:
iter = iter.children[bit ^ 1]
return xorDiff
def findMaximumXOR(self, nums: List[int]) -> int:
maxDifference = 0
trie = self.Trie()
for num in nums:
trie.insert(num)
for num in nums:
maxDifference = max(maxDifference, trie.searchForMostDifferent(num))
return maxDifference
class Solution {
private:
class TrieNode {
public:
vector<TrieNode*> children;
TrieNode() {
children = vector<TrieNode*>(2, nullptr);
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(int num) {
TrieNode* iter = root;
for (int i = 31; i >= 0; --i) {
int bit = (num >> i) & 1;
if (!iter->children[bit]) {
iter->children[bit] = new TrieNode();
}
iter = iter->children[bit];
}
}
int searchForMostDifferent(int num) {
TrieNode* iter = root;
int xorDiff = 0;
for (int i = 31; i >= 0; --i) {
int bit = ((num >> i) & 1) ^ 1;
if (iter->children[bit]) {
iter = iter->children[bit];
xorDiff |= (1 << i);
} else {
iter = iter->children[bit ^ 1];
}
}
return xorDiff;
}
};
public:
int findMaximumXOR(vector<int>& nums) {
int maxDifference = 0;
Trie trie;
for (int num : nums) {
trie.insert(num);
}
for (int num : nums) {
maxDifference = max(maxDifference, trie.searchForMostDifferent(num));
}
return maxDifference;
}
};
Time/Space Complexity:
- Time Complexity: O(n 32) + O(n 32) = O(n) we have
nnumbers of "length"32for insert and for finding the most different ones - Space Complexity: O(n)
nnumbers inserted into the trie (the binary representation length is bounded by the maximum integer, so it has constant contribution to complexity)
Explanation:
Of course, the first question you would ask is whether we only have positive numbers, since by the problem statement we do, we can use our implementation. Since we're talking about XOR, it's natural to ask the question if the numbers would be represented in binary form, how we would find the biggest difference between any of those numbers. Remember that XOR produces 1 if bits are different (one bit 0, and the other 1), so it would make sense to base our search for the most distant XOR element in array for each of the elements based on binary representation. In other words a trie like structure could come in handy here, if we can insert number's binary representation in the trie, to find the its most distant XOR we would start with the MSB (most significant bit) and try to go in the opposite way in the trie (e.g. if for number we have MSB = 1 we would follow the edge 0 if that node exists in the children nodes for the current node). Each time we find an opposite bit we will set the corresponding bit to our XOR difference xorDiff |= (1 << i);. How can we extract bit from certain position? We can use bit operations like (num >> i) & 1 to shift the number for i places and then extract the bit (if the bit is 1 the result of 1 & 1 = 1, otherwise 0 & 1 = 0). To find the opposite bit we can use the bitwise XOR operation itself (bit ^ 1, if bit is 1 the result would be 0, otherwise if bit is 0 the result of the operation would be 1). We start with the MSB since we want to maximize our XOR difference, remember that "to the left" bits contribute more to the final value (when converted to integer).