Maximum XOR Pair
Python
Hard
5 views
Problem Description
Read n integers, find maximum value of ai ^ aj over all pairs. Output the maximum XOR.
Input Format
First line n. Second line n integers.
Output Format
One integer maxXor.
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
trie=[[-1,-1]]
END=0
def insert(x):
node=0
for b in range(30,-1,-1):
bit=(x>>b)&1
nxt=trie[node][bit]
if nxt==-1:
trie[node][bit]=len(trie)
trie.append([-1,-1])
nxt=trie[node][bit]
node=nxt
def query(x):
node=0
val=0
for b in range(30,-1,-1):
bit=(x>>b)&1
want=1-bit
nxt=trie[node][want]
if nxt!=-1:
val |= (1<<b)
node=nxt
else:
node=trie[node][bit]
return val
insert(a[0])
best=0
for x in a[1:]:
v=query(x)
if v>best:
best=v
insert(x)
sys.stdout.write(str(best))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!