Interview Question
Country: United States
Nice one, this is the right solution!
I'd recommend changing this:
int m = 1;
while (!(z & m))
m <<= 1;
To this:
int m = z ^ (z-1);
XOR-ing the number to it's -1 decremented pair will give you the rightmost set bit.
(Of course your solution works too).
How is this case when the two distinct elements differ in more than 1 bit handled here?
Suppose, z = x^y = 1100 . Then,
a = 1100, b = 0000
a = 1000, b = 0100
both are valid solutions...
Adam: Yeah, you could also just use (a[i] & z == z) and (a[i] & z == z).
Anonymous: You're not recovering x and y uniquely from z alone. You're using z as a "separator mask" for a second pass over the arrays.
xor solution is nice.. as an alternative we can compute
the sum and sum of squares which for 32-bit numbers won't produce an overflow (or we can work with 64-bit ints instead which wont change the complexity)
thus we get: x + y = SUM_A - SUM_B
x^2 + y^2 = SUMSQ_A - SUMSQ_B
from there x and y can be easily computed.
Actually the mask should be
m = z ^ ~(z-1)
this will solve any number of bit changes in the two distinct numbers we want to find.
Add the numbers in both the arrays to get their sums : S1 , S2. Where
S1 = a[0] + a[1] + X + Y+ ..+a[n]+a[n+1] &
S2 = b[0] + b[1] .. + b[n-2] + b[n-1]
so X + Y = S1 - S2
Iterate through the arrays again and get the product of the elements in each array : P1 , P2
P1 = a[0] * a[1] * X * Y * ..a[n]*a[n+1]
P2 = b[0] * b[1] * .. b[n-2] * b[n-1]
So X*Y = P1/P2
We now have 2 equations :
X +Y = S1 - S2 &
X*Y = P1/P2
We can solve these to get the missing numbers in array b - X & Y. This will require 2 iterations of both the arrays. So the time complexity is O(n) and space is O(1).
The only downside of this technique is that if any of the array element is 0, this will not work.
Not the only downside. The really big downside is that this isn't an O(n) algorithm. The multiplies can be expected to overflow, and therefore you won't be able to use ordinary int or long variables. After n multiplications you can expect your total to have O(n) digits, which means that multiplying it just once with something else is O(n) or worse. So if a single multiply is O(n), this algo is O(n^2) at best. And...if you're going to spend O(n^2) time, you might as well just implement the naive compare-all-pairs algorithm.
You could fix the 0 problem by counting the number of 0s explicitly, but that won't change the O(n^2) performance.
I do think your solution is the frequently-given solution to this problem, however. I've been asked this exact question in an interview with a financial firm before, and your answer was the answer my interviewer was expecting me to get. When I gave the same rebuttal I've presented just now, the interviewer realized that he was wrong and let me advance to the next round.
In interviews, I've actually been asked several questions to which the expected answers were wrong. It happens.
hmmm. True. This solution works only for smaller number of elements where their products do not overflow. Were you able to get a proper solution for this problem ?
And when we say smaller number of elements, we would really have to mean very, very small. Even if all entries in the array are < 100, we'd want n < 10 even for a 64-bit variable.
The top-voted solution here (by psykotic) appears to be correct and truly O(n).
And as to your question as to whether I got a proper solution during the interview, no, since our time was spent discussing why this solution wasn't O(n). However, as the interviewer was also unable to come up with a correct solution, I advanced to the next round with flying colors.
eugene..i don't understand what you mean by 100 and 10. Are you talking saying <=10 entries with a value of 100 or less? Doesn't look like this would overflow in 64 bit. Am I missing something?
First, I assume you know how to solve the simpler problem when A and B have size n+1 and n and they differ by only one element, where you just XOR all the elements of both arrays together and all the common values cancel each other out, leaving the unique value.
The problem for two elements is a reduction to that special case. If you XOR all the elements of A and B then you get z = x ^ y as the result. Since x and y are presumed distinct, they must differ in at least one bit, and hence z must be nonzero in at least one bit, let's say the i-th. That partitions each of A and B into two parts, one where elements have 0 in their i-th bit, and one where elements have 1 in their i-th bit. By construction, x and y occur in separate parts, so we get a reduction to the earlier special case.
The code would look something like this:
- psykotic February 09, 2012