## Interview Question

• 0

Country: United States

Comment hidden because of low score. Click to expand.
8
of 8 vote

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:

``````#include <stdio.h>

void missing(int n, int *a, int *b, int *x, int *y)
{
int z = 0;
for (int i = 0; i < n; i++)
z ^= a[i];
for (int i = 0; i < n-2; i++)
z ^= b[i];

int m = 1;
while (!(z & m))
m <<= 1;

*x = 0;
*y = 0;
for (int i = 0; i < n; i++) {
if (a[i] & m)
*x ^= a[i];
else
*y ^= a[i];
}
for (int i = 0; i < n-2; i++)	{
if (b[i] & m)
*x ^= b[i];
else
*y ^= b[i];
}
}

int main()
{
int a[] = {5,1,2,6,3,4};
int b[] = {1,2,3,4};
int x, y;
missing(sizeof(a) / sizeof(*a), a, b, &x, &y);
printf("x=%d y=%d\n", x, y);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

m = z ^ ~(z-1)
this will solve any number of bit changes in the two distinct numbers we want to find.

Comment hidden because of low score. Click to expand.
0

Really neat algorithm

Comment hidden because of low score. Click to expand.
0

Really neat algorithm

Comment hidden because of low score. Click to expand.
0

Really neat algorithm

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

agreed :) the XOR based solution is better ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

I'm saying that in order for it to not overflow for values ~100, you'd want n < 10 or so.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another way could be to use a hashtable sort of data structure. Iterate over array b once and store everything into the hashtable. Now iterate over array a and see which ones are missing. this can be achieved in java using hashmap.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another way could be to use a hashtable sort of data structure. Iterate over array b once and store everything into the hashtable. Now iterate over array a and see which ones are missing. this can be achieved in java using hashmap.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I wrote a line of code like
pB[i] & m == 0

but what I really mean is (pB[i] & m) == 0
then I got trouble

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Another way could be to use a hashtable sort of data structure. Iterate over array b once and store everything into the hashtable. Now iterate over array a and see which ones are missing. this can be achieved in java using hashmap.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.