Author |
Topic: Find maximum XOR (Read 5016 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Find maximum XOR
« on: Nov 28th, 2009, 11:02pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Find maximum XOR
« Reply #1 on: Nov 28th, 2009, 11:06pm » |
Quote Modify
|
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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find maximum XOR
« Reply #2 on: Nov 29th, 2009, 7:34am » |
Quote Modify
|
It was asked before here. 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Find maximum XOR
« Reply #3 on: Nov 29th, 2009, 8:27am » |
Quote Modify
|
A solution from this thread.
on Apr 20th, 2008, 8:54am, 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?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Find maximum XOR
« Reply #4 on: Nov 29th, 2009, 9:00am » |
Quote Modify
|
Towr's solution looks good but i cannot think of a method of taking opposite paths in different subtrees. Can somebody help.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find maximum XOR
« Reply #5 on: Nov 29th, 2009, 11:18am » |
Quote Modify
|
on Nov 29th, 2009, 8:27am, 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 Nov 29th, 2009, 9:00am, 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.
|
| « Last Edit: Nov 29th, 2009, 11:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find maximum XOR
« Reply #6 on: Nov 30th, 2009, 4:09am » |
Quote Modify
|
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 (x y 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')  O(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'.
|
| « Last Edit: Nov 30th, 2009, 4:37am by Hippo » |
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: Find maximum XOR
« Reply #7 on: Dec 1st, 2009, 3:49pm » |
Quote Modify
|
on Nov 29th, 2009, 11:18am, 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)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print