Given an array A of N positive numbers and an integer P. Let NumPairs, be the number of pairs of elements of array A, such that their bitwise xor equal to X. You need to find the largest X, such that NumPairsx is greater or equal to P. If no such X exists print -1. Constraints:
N <=10 pow 4 P <=10 pow 9 Ai <=10 pow 9
Example:
A [1,12,13,14], P=1
QUESTION IS FROM PREVIOUS YEAR COMPANY QUESTIONS NOT FROM ANY ONGOING CONTEST
hmmm very normal title, surely it isn't from an on-going coding test, right?
Since N goes only up to 10^4, I imagine you can simply find all possible pairs of elements in the array and count NumPairs for all possible values of X. Something like...
Should suffice.
You should probably put all of the values into an array and then sort it as unordered map has a relatively large memory constant in addition to its large time complexity constant (it performs a bit better than std::map which is notoriously slow). However I still think that sorting the array is a bit too slow, albeit faster than using map or unordered map.
Do you mean use coordinate compression to reduce down the complexity to N^2 log N^2? If so, then you're absolutely correct, that would probably speed up the algorithm, although in retrospect I do realize that O(10^9~) would probably not fly. I suppose one could trade off the incredibly massive space complexity (of creating an array of size 10^9) for an equally unacceptable time complexity for this problem, but I guess OP should look for a better solution realistically. I think he could solve this with bitmasking and a trie, although I do not have a specific solution in mind.