\nIdea is to store the numbers in their binary representation. Let’s consider the X<\/code> in bitwise and from the highest bit of X=>i<\/code> to lowest bit 0<\/code>. The remaining numbers can be divided into two set one with set(1) bit at the bit position i and the other with unset(0) bit at the bit position i<\/code>, if the bit in the ith position of X<\/code> is set then we would consider all the numbers with unset bit and neglect the other half similar for when ith bit in the X<\/code> being unset.<\/p>\n<\/blockquote>\nDescription:<\/h4>\n\nWe will use trie<\/strong> to solve this problem.
\nA Trie<\/strong> is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of atmost 26<\/code> children and edges connect each parent node to its children. These 26<\/code> node pointers is for 26<\/code> letters of the English alphabet. A separate edge is maintained for every edge.
\nWe will build a trie with height being most significant bit of the largest number. To search in the Trie, we start with the first diverging point in the trie. For example, given [9, 10, 14, 13], or [1001, 1010, 1110, 1101], we start with the second bit, because all numbers is set on the first bit. The trie is also a balanced one, because each number is represented by a path whose length is equal to the trie height. For example, given [3, 10, 5, 25, 2, 8], the numbers are represented by 00011, 01010, 00101, 11001, 00010, 01000 in the trie.
\nNow, the starting point is the first trie node having two diverging sub-tries on the left and on the right. We try to go opposite branches(0 versus 1) in the respective sub-tries whenever possible. Sometimes we have two choices and we try them both, and sometimes we are forced to go in the same branch because that’s the only option.<\/p>\n<\/blockquote>\nAlgorithm :<\/h4>\n
insert()<\/strong>:<\/p>\n\n- \n
iterate for every integer i<\/code> in array, arr[]<\/code>, and store the number in its binary representation.<\/p>\n<\/li>\n- \n
check if the number (0 or 1) previously being inserted,<\/p>\n<\/li>\n
- \n
if not, make a new tree node for this number and add it as the children of the root.<\/p>\n<\/li>\n
- \n
it is already present, make the child node as parent and do the same with the remaining bits .<\/p>\n<\/li>\n
- \n
After inserting the last bitr node of i<\/code> in tree , update the weight of the last bit of i<\/code>, (temp->value = key)<\/code>.<\/p>\n<\/li>\n<\/ul>\nmaxXOR<\/strong> <\/p>\n\n- \n
iterate for every integer i<\/code> in array, arr[]<\/code>,<\/p>\n<\/li>\n- \n
for every i<\/code>, find the current bit in the prefix,<\/p>\n<\/li>\n- \n
if there is no same bit then look for opposite bits<\/p>\n<\/li>\n
- \n
else, look for prefix which has same bits.<\/p>\n<\/li>\n
- \n
return xor value of maximum bit difference value so we get maximum xor value .<\/p>\n<\/li>\n
- \n
Update xor value for every i<\/code>.<\/p>\n<\/li>\n<\/ul>\nComplexity Analysis :<\/h3>\n\nWe are inserting all the elements of array of size N<\/code>, lets say. Also we are searching for N<\/code> intereger values of the array at a time for a single query.
\nSpace complexity<\/strong> of this data structure would be O(2*N)<\/code>, where N<\/code> is the length of array.<\/p>\n<\/blockquote>\nSolutions:<\/h3>\n
\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1647244467734-Article_523.png\")
<\/p>\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2020\/06\/xora.png\")
<\/p>\n