The following puzzle was given to me by a friend who claimed it was given in a Google interview. If you can confirm or debunk this claim just post a comment - until then I am sure the headline will generate some traffic .

The original question as it was given to me was:

Given an array with 2n+1 integer elements, n elements appear twice in
arbitrary places in the array and a single integer appears only once
somewhere inside. Find the lonely integer with O(n) operations and O(1)
extra memory.

Now let’s transform this to a more digital-design-like problem. Given an SRAM of depth N and some arbitrary width K, which is filled with 2n+1 non zero values (for completeness - the rest of the 2^N - (2n+1) are all zeroes). n elements appear twice - in different places in the SRAM, while a single value appears only once.

Design a circuit with the minimum amount of hardware to find the value which appears only once.

### Comments (10) -

Add comment

biuquote

- Comment
- Preview

(b) It’s obvious that it can’t be done in n operations. 50% of the times your algorithm (or any other) won’t even get to read the lonely integer in the first n operations.

(c) O(2) = constant = O(1)

Sln is gr8 but doesnt it meets the exact requirement of the problem:

Sln should be solved in N Operations with O(1) extra memory — this particular sln takes 2n+1 operations and O(2) of memory.

algorithm:

int solution(int* arr)

{

int i, res;

for (i=res=0; i<2n+1; i++) res^= arr[i];

return res;

}

have a (2N+1) XOR gate and apply the same logic to store value in a k-bit register.

in k iterations you will get answer in your k-bit register.

start with lsb, x bit counter will count no. of 1s in lsbs of all 2n+1 digits. Then 2nd bits and so on upto msbs (kth bits).

LSB of the counter is assigned to the corresponding value in your k-bit register, when full- is your answer.

repeat this step for 2n+1 times. values stored in K bit register, will be rquired answer.

int solution(int* arr)

{

int i, res;

for (i=res=0; i<2n+1; i++) res^= arr[i];

return res;

}

hardware:

connect an N-bit counter to the address line of the SRAM and XOR the Data_Out with a K-bit register. When the counter overflows the value in the register will be the answer.

I am sure you will hit yourself on the head seeing the more simple solution.

Think simple! and thanks for sharing your thoughts online.

If you pair all elements starting from the first array item you need (2N-1) operations for the first search. The next paring search will be 2N-2 and so on. The amount of operations sums up to: (2N-1)+(2N-2)+…+(2N-(2N-1)) (note that you have 2N-1 sum terms in total). I always thought that these kind of algorithm is in O(N^2). Since it appears that for each item you have to touch more than a constant amount of others.

But apparently they are not.

(2N-1)+(2N-2)+…+(2N-(2N-1))

= (N-1)2N-(1+2+…+(2N-1))

= (N-1)2N - (2N-1)(2N)/2

= … cancel out …

= N

which is in O(n)… well that’s not exactly the solution in terms of hardware but explains why the algorithm is better than I thought

I hope that this is correct, I literally used yesterday’s shopping list to write down the calculation…

and an item might appear 4 times or any number of even or odd times - you will then have to pair the items and find the odd one out.

remember - the idea is to use the minimal amount of hardware!

is the algorithm allowed to be destructive on the dataset? In other words: can I mess up the array as long as I find the item? Are all the n+1 items mutually different, or is it allowed to encounter let’s say four times “5″?