Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
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.
Use XOR to find it.
ReplyDeleteXOR elements of A with those in B. Whatever remains is the extra element? Are the n elements distinct?
ReplyDeleteVery easy of course. But it makes me think of interesting followup variants.
ReplyDeleteWhat 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.
ReplyDeletea[0] xor a[1] xor .... a[n] xor b[0] xor b[1] xor ... b[n+1] will give the correct answer
x = Sum(B) - Sum(A)
ReplyDelete