I have two sets, $A$ and $B$, which both contain a large amount of hashed values. What is the most efficient way of computing:

$$\min_{i,j} A_i \otimes B_j$$

  • 1
    $\begingroup$ Hint: What is the smallest possible pair-wise XOR value? Can you think of an efficient way to find a pair that produces this value? $\endgroup$ – j_random_hacker Apr 1 at 0:56
  • $\begingroup$ Well, the minimum is clearly 0, so I'm not sure where your hint is leading exactly. My guess would be to build a trie for B, and then check how far we can go down that trie with the complement of each element of A. $\endgroup$ – yawn Apr 1 at 1:51
  • 1
    $\begingroup$ Sounds like you have an answer. Is there a reason you've rejected that? If you're asking whether it is possible to do better, it would be useful to edit the question describe the best algorithm you know of and analyze its running time. $\endgroup$ – D.W. Apr 1 at 2:15
  • $\begingroup$ What is “large”? 100? A million? A billion? $\endgroup$ – gnasher729 Apr 1 at 6:01
  • $\begingroup$ It would be totally easy if both arrays were sorted. $\endgroup$ – gnasher729 Apr 1 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.