package main

import (
	"fmt"
	"sort"
)

// 二叉树解法
type Tire struct {
	Nodes [2]*Tire
}

func (t *Tire) Insert(num int) {
	node := t
	// 以二进制的视角从高位往低位遍历num
	for i := 31 ; i >= 0 ; i -- {
		// 往左边走
		if num & (1 << i) > 0  {
			if node.Nodes[0] == nil {
				node.Nodes[0] = &Tire{}
			}
			node = node.Nodes[0]
		}else {
			// 往右边走
			if node.Nodes[1] == nil {
				node.Nodes[1] = &Tire{}
			}
			node = node.Nodes[1]
		}
	}
}

func (t *Tire) Search(num int) int {
	node := t
	res := 0
	for i := 31 ; i >- 0 ; i -- {
		// 当前位为1，在Tire中优先寻找为0的node
		if num & ( 1 << i ) > 0  {
			if node.Nodes[1] != nil {
				node = node.Nodes[1]
				res += 1 << i
			}else {
				node = node.Nodes[0]
			}
		}else {
			if node.Nodes[0] != nil {
				node = node.Nodes[0]
				res += 1 << i
			}else {
				node = node.Nodes[1]
			}
		}
	}
	return res
}


func findMaximumXOR1(nums []int)  int {
	t := &Tire{}
	for _ , v := range nums {
		t.Insert(v)
	}
	res := 0
	for _ , v := range nums {
		res = max(res , t.Search(v))
	}
	return res
}




// 暴力解法
func findMaximumXOR(nums []int) (res int) {
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})
	maxNum := nums[0]
	for i := 0 ; i < len(nums) && nums[i] > ( maxNum >>  1 ) ; i ++  {
		for j := i ; j < len(nums) ; j ++ {
			res = max(res, nums[i] ^ nums[j])
		}
	}
	return res
}

func max(a , b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Println(findMaximumXOR1([]int{3,5}))
}