Array with 2n+1 integer elements puzzle

Tags: | Posted by Admin on 10/28/2008 9:46 AM | Comments (10)

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

Norman on 10/27/2008 12:46 PM (a) The requirement was: ‘Find the lonely integer with O(n) operations…’ not N operations.

(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)
Lincoln on 10/27/2008 3:04 PM Following sln was given by Tzachi -

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;
}
Foster on 10/27/2008 5:22 PM Or even more simple way is
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.
Dillon on 10/27/2008 7:40 PM How about a x bit counter such that 2^x >= 2N+1; and a 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.
Benjamin on 10/27/2008 9:58 PM read the 1st element from memory.store this output after xor-ing with K bit register(initial all ‘0′), in the same register.

repeat this step for 2n+1 times. values stored in K bit register, will be rquired answer.
Barrett on 10/28/2008 12:16 AM algorithm:
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.
Baldwin on 10/28/2008 2:34 AM I think you are over-complicating.
I am sure you will hit yourself on the head seeing the more simple solution.
Think simple! and thanks for sharing your thoughts online.
Adam on 10/28/2008 4:52 AM If it boils down to pairing I was very skeptical about the complexity.
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 Smile
I hope that this is correct, I literally used yesterday’s shopping list to write down the calculation…
David on 10/28/2008 7:10 AM you can destroy the contents if you wish although it is not necessary IMHO.
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!
Stallone on 10/28/2008 9:28 AM Hi,
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″?

Add comment




  Country flag
biuquote
  • Comment
  • Preview
Loading