Ugly but straight forward Python Trie solution, first build a Trie with all the nums; then try to "pass" each num in nums through that Trie,
if the path bifurcates at a node, took the opposite route,and update the current XOR result by adding 1 to the current bit.
class Solution(object): def findMaximumXOR(self, nums): """ :type nums: List[int] :rtype: int """ head=[None,None] for num in nums: node=head for bit in range(31,-1,-1): chd=int(bool(num&(1<<bit))) if node[chd]==None: NewNode=[None,None] node[chd]=NewNode node=NewNode else: node=node[chd] maxXor=0 for num in nums: node=head curXor=0 for bit in range(31,-1,-1): chd=int(bool(num&(1<<bit))) if node[1^chd]: curXor|=1<<bit node=node[1^chd] else: node=node[chd] maxXor=max(maxXor,curXor) return maxXor
@stould No, it's O(NlogV) = O(32 * N) = O(N)
can you explain or add comment to your code please
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.