Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Use XOR to find it.
XOR elements of A with those in B. Whatever remains is the extra element? Are the n elements distinct?
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.)
Once again xor bit operation comes in handy. a xor a xor .... a[n] xor b xor b xor ... b[n+1] will give the correct answer
x = Sum(B) - Sum(A)