leetcode-go/leetcode/medium/421.maximum-xor-of-two-numbers-in-an-array.go

func findMaximumXOR(nums []int) int {
	max, mask := 0, 0
	for i := 31; 0 <= i; i-- { // Check max & 1<<i is 1 or 0
		m := make(map[int]bool)
		mask |= 1 << uint(i)
		for _, n := range nums {
			m[n&mask] = true // Get the top n digit of nums as prefix set
		}
		tmp := max | 1<<uint(i) // Assume that c == max | 1<<i, for each a, find if b is in prefix set
		for k := range m {
			if _, ok := m[tmp^k]; ok {
				max = tmp
				break
			}
		}
	}
	return max
}