###### tags: `Leetcode` `medium` `bit` `python` `c++`

# 421. Maximum XOR of Two Numbers in an Array

## [題目連結:] https://leetcode.com/problems/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

## 解題想法:
* 此題為，给一個數組nums ，求nums[i] XOR nums[j] 的最大结果，其中 0 ≤ i ≤ j < n 。
* 使用bits判斷: (Ps.本人超討厭bits相關題目 (´･_･`) )
* for (int bit=31; bit>=0; bit--)
* 使用位運算，從**高位**到**低位**依次決定每個位數是1or0
* 其中checkSet: 用set紀錄，nums中的數字分別除bit次2的冪方
* 再逐一判斷checkSet中的元素: item
* 若希望最大結果: res+1
* 與item xor後，存在於checkSet中: **表示當前位置可以為1**
* 所以將res正式+1，then break

## Python:

class Solution(object):
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #從最高位bit做check
        #32bit 32+31bit 32+31+30bit...........逐一check最大的 -> key
        res=0
        for bit in range(31,-1,-1):
            res<<=1
            #-> key
            checkSet = set(n>>bit for n in nums) #狂右移除2的冪方(同下面三句)
            #checkSet=set()
            #for n in nums:
            #   checkSet.add(n>>bit)
            for item in checkSet:
                #若希望的最大結果:res+1
                #與item xor後 存在於checkSet中 表示該bit可以為1 
                if (res+1)^item in checkSet:
                    res+=1
                    break
        return res
nums = [3,10,5,25,2,8]
result=Solution()
ans=result.findMaximumXOR(nums)
print(ans)

## C++:

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int res=0;
        for (int bit=31; bit>=0; bit--){
            res<<=1;
            unordered_set<int> checkSet;
            //collect 
            for (auto n: nums){
                checkSet.insert(n>>bit);
            }
            //check
            for (auto item: checkSet){
                auto tmp=(res+1)^item;
                if (checkSet.find(tmp)!=checkSet.end()){
                    res+=1;
                    break;
                }
            }
        }
        return res;
    }
};