If I have a list L of positive integers and I am given another number K , I need to find the number in the list with which XOR of K is maximum. I have thought of an algorithm for this. I want to verify its correctness with counter arguments. My algorithm is: Find P =K's complement (1's complement). Now find the number which is closest to P in the list L. Let this number be N. The XOR of K and N will be maximum. Closest number to a number I in a given set of numbers is a number whose difference with I is minimum. Lets say, it is not correct for the numbers greater than P in the list L . But isn't it correct for the numbers <=P ? Please tell me whether I am correct or not by providing counter arguments/suggestions/ideas.

Reputation: 2942

maximum xor is with closest number

If I have a list L of positive integers and I am given another number K, I need to find the number in the list with which XOR of K is maximum.

I have thought of an algorithm for this. I want to verify its correctness with counter arguments. My algorithm is:

Find P=K's complement (1's complement). Now find the number which is closest to P in the list L. Let this number be N. The XOR of K and N will be maximum.
Closest number to a number I in a given set of numbers is a number whose difference with I is minimum.

Lets say, it is not correct for the numbers greater than P in the list L. But isn't it correct for the numbers <=P ?

Please tell me whether I am correct or not by providing counter arguments/suggestions/ideas.

Upvotes: 1

Answers (3)

iloahz

Reputation: 4561

i think you need something called a Trie.

consider every bit of K, from higher to lower, of course we can be greedy when determine whether this bit of answer can be 1, i mean, first you try your best to get 1024(or even higher), and then 512, and then 256 and then......finally to the last bit 1.

So first you need to check whether some number in the list L has the opposite value to K in the highest bit, then among all the chosen numbers, then you need to find the numbers which has the opposite value to K in the second highest bit.

now the solution is obvious, build a Trie with L, determine the answer's bits from higher to lower, which corresponds to travel on that tree.

Upvotes: 2

nneonneo

Reputation: 179592

No, not right.

Let K = 0011, so that P = 1100. Let L = {0011, 1100}. Your algorithm would choose N = 1100, which is obviously incorrect since N^K = 0, while 0011^N = 3.

Upvotes: 0

WaywiserTundish

Reputation: 122

Coding and running the obvious brute-force algorithm would have taken far less time than you've already spent on this.

Upvotes: -1

maximum xor is with closest number

Answers (3)

Related Questions