Wednesday, November 17, 2010

Arrays comparison. don't always sort them.

Two arrays are given A[n] and B[n+1]. Array A contains n integers and B contains n+1 integers of which n are same as in array B but in different order and one extra element x. Find x.


  1. XOR elements of A with those in B. Whatever remains is the extra element? Are the n elements distinct?

  2. Very easy of course. But it makes me think of interesting followup variants.

    What if there were TWO extra integers in B. Can you find them BOTH easily?

    What if A and B are the same length but one element differed? Can you find that element in both A and B easily?

    The obvious programmer solution is a hash table, but that doesn't have the elegance of a much more clever method!
    Hint below:

    (Hint: no hash, no sorting, O(1) storage, use a little algebra.)

  3. Once again xor bit operation comes in handy.
    a[0] xor a[1] xor .... a[n] xor b[0] xor b[1] xor ... b[n+1] will give the correct answer