- Maximum Xor
- Discussions

# Maximum Xor

# Maximum Xor

+ 10 comments This was a fun problem.

I'll assume the non-efficient solution is obvious for most people.

rene_d's hint about using a Trie is key here, as it's critical for getting O(n) efficiency out of the problem.

I had never encountered a Trie before, so I had to grabble with it a bit before it made intuitive sense here.

If you look up how a bitwise Trie is structured, you'll get an idea that it's a binary tree where each 1 or 0 bit at each position in a given integer points to another node. If you were to draw out any given value in a binary tree, you'd follow all 32-bits down, with 0 bits going left and 1 bits going right, until you reached a leaf node, and then you'd find the value you are searching for.

If you take the input array of this problem and build a Trie out of all of the values in the array, you'd get a large tree with lots of values branching off from the various bit positions.

How that helps you solve the maximum XOR problem is that you can do a query in the Trie to help you find what best possible XOR out of the possible choices.

What's the best possible XOR companion value? It's one where all of the bits are the exact opposite of the candidate value.

For example, if your query value (let's use nibbles for this discussion for conciseness) has a bit pattern of 0010, then the best possible XOR companion value would be 1101, which would give you a result of 1111.

With a Trie query, you can see if there's a branch at the opposite bit value at each bit position. In the example above, for the MSB of 4, you'd try and see if there was a branch with a bit value of 1; in this case there is, but if not then you would take the branch with a bit value of 0 since that path actually exists.

The end result is that you can query the Trie quickly and find the best possible match for every single query.

+ 3 comments my concise solution wich runs in O(n):

def maxXor(arr, queries): ans = [] trie = {} k = len(bin(max(arr+queries))) - 2 for number in ['{:b}'.format(x).zfill(k) for x in arr]: node = trie for char in number: node = node.setdefault(char, {}) for n in queries: node = trie s = '' for char in'{:b}'.format(n).zfill(k) : tmp = str(int(char) ^ 1) tmp = tmp if tmp in node else char s += tmp node = node[tmp] ans.append(int(s, 2) ^ n) return ans

+ 2 comments #include<bits/stdc++.h> using namespace std; struct trie{ trie *child[2]; bool is_end; }; trie *new_node() { trie *temp=new trie; temp->child[0]=NULL; temp->child[1]=NULL; temp->is_end=false; return temp; } void insert(trie *root,int x) { trie *temp=root; int index; for(int i=31;i>=0;i--) { if(x&(1<<i)) index=1; else index=0; if(temp->child[index]==NULL) temp->child[index]=new_node(); temp=temp->child[index]; } temp->is_end=true; } void search_result(trie *root,int x) { int cnt=0,index,index_; trie *temp=root; for(int i=31;i>=0;i--) { if(x&(1<<i)) index=1; else index=0; index_=(index+1)%2; if(temp->child[index_]!=NULL && temp->is_end==false) { cnt=cnt+pow(2,i) ; temp=temp->child[index_]; } else { temp=temp->child[index]; } } cout<<cnt<<endl; } void max_xor(int vec[],int n,int q[],int t) { trie *root=new_node(); for(int i=0;i<n;i++){ //cout<<"insert: "<<q[i]<<endl;; insert(root,vec[i]);} for(int i=0;i<t;i++) { //cout<<"q["<<i<<"]: "<<q[i]<<"="; search_result(root,q[i]); } } int main() { int n,x,t; cin>>n; int vec[n]; for(int i=0;i<n;i++) cin>>vec[i]; cin>>t;int q[t]; for(int i=0;i<t;i++) cin>>q[i]; max_xor(vec,n,q,t); return 0; }

+ 0 comments That was tough. Trie based Swift solution.

A few things it seems people aren't exploiting:

- you can test a bit by doing a division by 1 << bit position
- you can strip a MSB by doing a mod by 1 << bit position
- you can flip a bit by XOR with 1

// Complete the maxXor function below. struct BitTrie { class TrieNode { var children = Array<TrieNode?>(repeating: nil, count: 2) func add(value: Int, index: Int) { let bitPos = 31-index if bitPos < 0 { return } let power = 1 << bitPos let bit = value / power let remainder = value % power if let child = children[bit] { child.add(value: remainder, index: index+1) } else { children[bit] = TrieNode() children[bit]!.add(value: remainder, index: index+1) } } } let root = TrieNode() func add(_ value: Int) { root.add(value: value, index: 0) } func getMaxXor(_ value: Int) -> Int { var current = root var xorValue = 0 var remainder = value for i in 0..<32 { let bitPos = 31-i let power = 1 << bitPos let bit = remainder / power remainder = remainder % power if let child = current.children[bit^1] { xorValue += power current = child } else { current = current.children[bit]! } } return xorValue } } func maxXor(arr: [Int], queries: [Int]) -> [Int] { var maxVals = [Int]() let trie = BitTrie() for value in arr { trie.add(value) } for query in queries { maxVals.append(trie.getMaxXor(query)) } return maxVals }

Sort 54 Discussions, By:

Please Login in order to post a comment