CareerCup

I presume maximum result means that the result eventually obtained on XOR is maximum:

Thus one should start from MSB:
Function Split: Divides list of numbers into 2 lists: list A contains all numbers starting with 1, MSB removed. list B contains all numbers starting with 0, MSB removed. eg. 1011, 0101, 1001 is divided into 2 lists: A:{011, 001}, B:{101}

given such a split, the candidate maximum XOR pair should have one coming from A and other coming from B...

Thus given A,B as above, applying recursion, candidate pair should come from one of (AA, BB) or (AB, BA). ie. (NULL, NULL) or ({11, 01}, {01})

Continue using induction. Avoid any pair containing at least one NULL list. Base condition is when both list have one element each. Recursion based on comparison.

Err ... The complexity seems N^2*x, where x is the number of bits per integer. Then why don't we just using for loops, it's complexity will be N^2 as well.

Is this not xor (n, xor(n)).. i.e n and xor(n) are the two integers?

what if xor(n) is not in the list...that is the problem...

I think if we sort the array and find the smallest and largest element and by XORing those two numbers we can find the maximum number.Any comments?????

use a compressed trie or suffix tree. based on the bit at each position of the number, generate the suffix tree. then pick the nodes which end up at numbers such that the difference in position of the bit on which they were last divided is maximum. if there are more than one number split at any of those bits, then compare the bit at that position and select the pair which differ at that bit. consider the following example: S={1,6,7}
S
| \
001 /\
110 111 (bit 3)
001 is obtained on split at bit position 1. at bit position 3, we obtain split on 6,7. the maximum difference is between numbers differing at bit positions 1 and 3. hence it can be {1,6} or {1,7}. but now, check bit position 3. 1,6 differ at 3 but 1,7 dont. hence {1,6} give the maximum difference.

How about this?
Just biggest number should have 1 in the height bit field.
Example, Assuming that binary are {1000, 0111, 0110, 0001}
1000 -> 8 is biggest number.
than adjust XOR all number with the biggest number in the array again and get the biggest result.

The Big O would be
1. finding biggest number O(n)
2. Adjusting XOR all element in the Array with biggest number O(n) and finding biggest result.
3. print out two numbers.
===> O(n)

Is there something I missed? 2EZ...

n*x approach ...x is no. of bits

find maximum no. O(n)
now traverse array again and take XOR with each element to find the largest.