# 421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤  ij  <  n.

Could you do this in O( n ) runtime?

Example:

``````Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.
``````

3        10        5        25        2        8

11      1010     101     11001     10      1000

3        10        5        25        2        8

11      1010     101     11001     10      1000

3        10        5        25        2        8

11      1010     101     11001     10      1000

3        10        5        25        2        8

11      1010     101     11001     10      1000

3        10        5        25        2        8

11      1010     101     11001     10      1000

``````class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int res = 0, mask = 0;
for (int i = 31; i >= 0; --i) {
unordered_set<int> s;
for (int num : nums) {
}
int t = res | (1 << i);
for (int prefix : s) {
if (s.count(t ^ prefix)) {
res = t;
break;
}
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/421

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/130427/()-92

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91049/Java-O(n)-solution-using-bit-manipulation-and-HashMap

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91064/C%2B%2B-22-ms-beats-99.5-array-partitioning-similar-to-quick-sort

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation