wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find maximum XOR
        
(Message started by: birbal on Nov 28th, 2009, 11:02pm)
Title: Find maximum XOR
Post by birbal on Nov 28th, 2009, 11:02pm
Given an integer array of length n, find 2 numbers which has maximum XOR.

the brute force method is 0(n2) assuming XOR operator takes O(1) time.

Can somebody give a better solution.
Title: Re: Find maximum XOR
Post by birbal on Nov 28th, 2009, 11:06pm
I am thinking of making a trie which looks like binary tree, with one bit at each node. This would take O(n log n ) time.
After this, start from the root node and go to opposite directions, merge the two subtree and repeat the procedure until u see a leaf.

Im not sure how much time merge operation will take.
Title: Re: Find maximum XOR
Post by towr on Nov 29th, 2009, 7:34am
It was asked before here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1208704026;). But that thread doesn't really offer anything that you haven't suggested yourself.

You shouldn't merge the two subtrees though, because then you risk xorring number not in your list.
Title: Re: Find maximum XOR
Post by R on Nov 29th, 2009, 8:27am
A solution from this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1208704026;) thread.


on 04/20/08 at 08:54:37, towr wrote:
Make a binary tree for all numbers (with most significant bit at the root), then try to find your way to the end taking paths in opposite direction as often as possible (such that you get a 1 when XORring).
It should have the same complexity as sorting, I think. (Because you create paired subsets at each step)

Not entirely sure that's clear; but I assure you it's utterly brilliant ;)

@towr
There can be more than one choice of taking opposite paths at some point. Right?
Title: Re: Find maximum XOR
Post by birbal on Nov 29th, 2009, 9:00am
Towr's solution looks good but i cannot think of a method of taking opposite paths in different subtrees. Can somebody help.
:(
Title: Re: Find maximum XOR
Post by towr on Nov 29th, 2009, 11:18am

on 11/29/09 at 08:27:32, R wrote:
@towr
There can be more than one choice of taking opposite paths at some point. Right?
Yes, you get sets of pairs. You can have many pairs of numbers that give the same maximum. You could do a depth-first search among them.
For every path in the tree from root to leaf (or in other words every number in the list), you can easily find the "maximally opposite" path that maximizes the XOR.


on 11/29/09 at 09:00:54, birbal wrote:
Towr's solution looks good but i cannot think of a method of taking opposite paths in different subtrees. Can somebody help.
All it means is that if in one case you chose a one, than in the other you chose a zero, or vice versa.
Title: Re: Find maximum XOR
Post by Hippo on Nov 30th, 2009, 4:09am
At first:
Question  ...  can x be obtained as a XOR of two numbers in the set is relatively easy ... Randomized O(n).
... the same algorithm as testing given sum ... or any "reversible" operation ... using hash.

At second ... for given mask testing x can be obtaind as a XOR of two numbers MOD given mask is easy as well (xhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gify MOD mask means here x & mask = y&mask).

So you can use binary search to get maximal obtainable x in O(n b) for b-bit numbers.

And yes, you can remove duplicates in O(n) and than b>log n' so you can sort the resulting list in O(n' log n') http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifO(n' b).

And yes, adding those with maximal bit set to the trie and checking for maximal match of those not having the bit set would solve the problem. (Trie would represent all needed hash versions at once).
Actually it would work in O(n' b) as well.

Example of bad inputs ... all odd numbers.
Having guessed for mask 1111111000 the xor would be 1111111000 would save a lot of work ... so may be use the n' for good start guess would speed up it a little bit. But it seems to me you only know best XOR would be at least n'.
Title: Re: Find maximum XOR
Post by inexorable on Dec 1st, 2009, 3:49pm

on 11/29/09 at 11:18:24, towr wrote:
Yes, you get sets of pairs. You can have many pairs of numbers that give the same maximum. You could do a depth-first search among them.
For every path in the tree from root to leaf (or in other words every number in the list), you can easily find the "maximally opposite" path that maximizes the XOR.

All it means is that if in one case you chose a one, than in the other you chose a zero, or vice versa.

In order to avoid dealing with pairs..

If a binary tree is constructed first such that each of leaf nodes corresponds to a number and internal node corresponds to the bit. we start with root having most significant bit.(something like a huffman tree where all numbers have equal probabilities, to have balanced tree ..).
Then for each number X if we traverse the tree till we reach leaf node(only going to same bit node as X if an opposite bit is not found)(pairs would not arise here since XOR resulting in 1 from a more significant bit is always > XOR resulting from rest of lesser significant bits). We would reach max opposite leaf for each number.
we can take max pair of all this values?

It is almost the same as what was discussed above. Just adding additional iteration on tree to find max pair, for simpler implementation.
It would still be O(nlogn)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board