Problem Statement:
Given an integer array A[1..N], find max value of A[i]^A[j] , where ^ is bitwise xor.
Input:
First Line contains N (1 < N <= 100000)
second line contains N non-negative integers seperated by space.(value of integer is < 32000)
Output:
Print the answer in a single line, followed by a '\n' ( just print a new line, no need to display '\n' ).
Sample Test Case:
Input:
5
1 10 20 30 40
Output:
60
Explanation:
XOR ing of 20 and 40 equals to 60, which is maximum of XOR ing of all other pairs.
Approach:
A data structure named trie is very useful for solving this problem. All we have to do is to construct a tree of binary representation of the numbers in the array and keep looking for 01-10 and 00-11 pairs. In case both 01-10 and 00-11 branches are encountered at the same level of the tree, compute the XOR for both the branches and select the maximum among them.
Code in C++:
Given an integer array A[1..N], find max value of A[i]^A[j] , where ^ is bitwise xor.
Input:
First Line contains N (1 < N <= 100000)
second line contains N non-negative integers seperated by space.(value of integer is < 32000)
Output:
Print the answer in a single line, followed by a '\n' ( just print a new line, no need to display '\n' ).
Sample Test Case:
Input:
5
1 10 20 30 40
Output:
60
Explanation:
XOR ing of 20 and 40 equals to 60, which is maximum of XOR ing of all other pairs.
Approach:
A data structure named trie is very useful for solving this problem. All we have to do is to construct a tree of binary representation of the numbers in the array and keep looking for 01-10 and 00-11 pairs. In case both 01-10 and 00-11 branches are encountered at the same level of the tree, compute the XOR for both the branches and select the maximum among them.
Code in C++:
Don't we need to malloc node or p->left,etc before using them ?? :/
ReplyDelete