• Solution

Approach #1 Brute force

it's takes O(n^2) time and O(1) space complexity.

Java

``````public class Solution {
public int findMaximumXOR(int[] nums) {
int ans = Integer.MIN_VALUE;
if (nums.length == 1)
return 0;
for (int i = nums.length-1; i >=0; --i){
for (int j = i-1; j>=0;--j){
ans = Math.max(ans,nums[i]^nums[j]);
}
}
return ans;
}
}
``````

Approach #2 TreeNode

It's takes O(n) time and O(2^32) space complexity.
The idea is the construct from binary numbers representation binary tree and after this iterate through this tree by each number.

C++

``````class Solution {
public:
class TreeNode {
public:
TreeNode* next[2];
TreeNode () {memset(next,NULL, 2*sizeof(TreeNode*));};
};
TreeNode* buildTree(vector<int>& nums) {
TreeNode* root = new TreeNode(), *cur;
int n = nums.size();
for (int i = 0; i < n; ++i) {
int num = nums[i];
cur = root;
for (int j = 31; j >= 0; --j) {
int index = ((num >> j) & 1);
if (!cur->next[index])
cur->next[index] = new TreeNode();
cur = cur->next[index];
}
}
return root;
}

int   helper(TreeNode* cur, int num) {
int res = 0;
for (int i = 31; i >= 0; --i) {
int index = ((num >> i) & 1) ? 0 : 1;
res <<= 1;
if (cur->next[index]) {
res |= 1;
cur = cur->next[index];
} else {
res |= 0;
cur = cur->next[index ? 0 : 1];
}
}
return res;
}

int findMaximumXOR(vector<int>& nums) {
int res = 0;
TreeNode* root = buildTree(nums);

for (auto & num : nums) {
res = max(res, helper(root, num));
}

return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.