We have unsorted array of hashes, each hash is a 64bit integer. We need to find the pairwise hamming distance in an array. What state the problem to find maximum Manhattan distance between points in 64Bit space where each dimension has only 0 and 1 state.
The simplest solution is:
- just pick each item one-by-one
- and compare (find the hamming distance) with the rest items starting for this one.
That gives us $O(N^2)$ complexity, where $N$ is length of list. But can we do better because of nature of Hamming distance and nature of 64bit numbers? Could we use binary operations here?