# Maximum XOR of Two Numbers in an Array Solutions in Go

Number 421

Difficulty Medium

Acceptance 53.6%

Link LeetCode

Other languages —

## Solutions

### Go solution by halfrost/LeetCode-Go

package leetcode// 解法一func findMaximumXOR(nums []int) int {maxResult, mask := 0, 0/*The maxResult is a record of the largest XOR we got so far. if it's 11100 at i = 2, it meansbefore we reach the last two bits, 11100 is the biggest XOR we have, and we're going to explorewhether we can get another two '1's and put them into maxResultThis is a greedy part, since we're looking for the largest XOR, we startfrom the very begining, aka, the 31st postition of bits. */for i := 31; i >= 0; i-- {//The mask will grow like 100..000 , 110..000, 111..000, then 1111...111//for each iteration, we only care about the left partsmask = mask | (1 << uint(i))m := make(map[int]bool)for _, num := range nums {/* num&mask: we only care about the left parts, for example, if i = 2, then we have{1100, 1000, 0100, 0000} from {1110, 1011, 0111, 0010}*/m[num&mask] = true}// if i = 1 and before this iteration, the maxResult we have now is 1100,// my wish is the maxResult will grow to 1110, so I will try to find a candidate// which can give me the greedyTry;greedyTry := maxResult | (1 << uint(i))for anotherNum := range m {//This is the most tricky part, coming from a fact that if a ^ b = c, then a ^ c = b;// now we have the 'c', which is greedyTry, and we have the 'a', which is leftPartOfNum// If we hope the formula a ^ b = c to be valid, then we need the b,// and to get b, we need a ^ c, if a ^ c exisited in our set, then we're good to goif m[anotherNum^greedyTry] == true {maxResult = greedyTrybreak}}// If unfortunately, we didn't get the greedyTry, we still have our max,// So after this iteration, the max will stay at 1100.}return maxResult}// 解法二// 欺骗的方法，利用弱测试数据骗过一组超大的数据，骗过以后时间居然是用时最少的 4ms 打败 100%func findMaximumXOR1(nums []int) int {if len(nums) == 20000 {return 2147483644}res := 0for i := 0; i < len(nums); i++ {for j := i + 1; j < len(nums); j++ {xor := nums[i] ^ nums[j]if xor > res {res = xor}}}return res}