Maximum XOR of Two Numbers in an Array – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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 * 1050 <= nums[i] <= 231 - 1
C++ Maximum XOR of Two Numbers in an Array LeetCode Solution
int findMaximumXOR(vector<int>& nums) {
int n = nums.size();
if (n == 0 || n == 1)
return 0;
if (n == 2)
return nums.at(0) ^ nums.at(1);
list<int> set0;
list<int> set1;
int i;
int j;
int maxValue;
for (i = 30; i >= 0; i--) {
for (j = 0; j < n; j++) {
if ((nums.at(j) & (1<<i)) == 0)
set0.push_back(nums.at(j));
else
set1.push_back(nums.at(j));
}
if (set0.size() != 0 && set1.size() != 0) {
maxValue = pow(2, i);
break;
}
else {
set0.clear();
set1.clear();
}
}
if (i == -1)
return 0;
maxValue += getMaxXor(set0, set1, i-1);
return maxValue;
}
int getMaxXor(list<int>& set0, list<int>& set1, int pos) {
int maxValue;
list<int> set0list0;
list<int> set0list1;
list<int> set1list0;
list<int> set1list1;
int i;
list<int>::iterator it;
if (set0.size() == 0 || set1.size() == 0 || pos < 0)
return 0;
for (it = set0.begin(); it != set0.end(); it++) {
int value = *it;
if ((value & (1<<pos)) == 0)
set0list0.push_back(value);
else
set0list1.push_back(value);
}
for (it = set1.begin(); it != set1.end(); it++) {
int value = *it;
if ((value & (1<<pos)) == 0)
set1list0.push_back(value);
else
set1list1.push_back(value);
}
if (set0list0.size() == 0 && set1list0.size() == 0)
maxValue = getMaxXor(set0, set1, pos-1);
else if (set0list1.size() == 0 && set1list1.size() == 0)
maxValue = getMaxXor(set0, set1, pos-1);
else {
int maxValue1 = getMaxXor(set0list0, set1list1, pos-1);
int maxValue2 = getMaxXor(set0list1, set1list0, pos-1);
maxValue = pow(2, pos) + (maxValue1 > maxValue2 ? maxValue1 : maxValue2);
}
return maxValue;
}
Java Maximum XOR of Two Numbers in an Array LeetCode Solution
class Trie {
Trie[] children;
public Trie() {
children = new Trie[2];
}
}
public int findMaximumXOR(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
// Init Trie.
Trie root = new Trie();
for(int num: nums) {
Trie curNode = root;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode.children[curBit] == null) {
curNode.children[curBit] = new Trie();
}
curNode = curNode.children[curBit];
}
}
int max = Integer.MIN_VALUE;
for(int num: nums) {
Trie curNode = root;
int curSum = 0;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode.children[curBit ^ 1] != null) {
curSum += (1 << i);
curNode = curNode.children[curBit ^ 1];
}else {
curNode = curNode.children[curBit];
}
}
max = Math.max(curSum, max);
}
return max;
}
Python 3 Maximum XOR of Two Numbers in an Array LeetCode Solution
def findMaximumXOR(self, nums):
answer = 0
for i in range(32)[::-1]:
answer <<= 1
prefixes = {num >> i for num in nums}
answer += any(answer^1 ^ p in prefixes for p in prefixes)
return answer
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
