Introduction Link to heading
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 ≤ i, j < 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.
Solution Link to heading
Trie solution:
type trie struct {
f *trie
t *trie
}
func (root *trie) maxXor(num int) int {
v := 0
node := root
if node.f == nil && node.t == nil {
return 0
}
for i := 31; i >= 0; i-- {
ui := uint(i)
if ((num >> ui) & 1) > 0 {
if node.f != nil {
v |= (1 << ui)
node = node.f
} else if node.t != nil {
node = node.t
}
} else {
if node.t != nil {
v |= (1 << ui)
node = node.t
} else if node.f != nil {
node = node.f
}
}
}
return v
}
func (root *trie) save(num int) {
node := root
for i := 31; i >= 0; i-- {
ui := uint(i)
if ((num >> ui) & 1) > 0 {
if node.t == nil {
node.t = &trie{nil, nil}
}
node = node.t
} else {
if node.f == nil {
node.f = &trie{nil, nil}
}
node = node.f
}
}
}
func findMaximumXOR(nums []int) int {
if len(nums) < 2 {
return 0
}
root := &trie{nil, nil}
maxSoFar := 0
for _, num := range nums {
v := root.maxXor(num)
if maxSoFar < v {
maxSoFar = v
}
root.save(num)
}
return maxSoFar
}
Explanation Link to heading
Lets store all bits in Trie from the most significat to less significant (BigEndian). In this case when we will search best opposite bit for xor operation the most significant bit will play more important role in max result than all the rest bits.