Any Recommendations?
Author
Hi,
Recently my friend asked me a tricky c++ question:
An array has N elements with each element having a pair (ie: 3, 3) randomly distributed somewhere except ONE element that is unique. How do you identify this unique element in the array (constraints being a SINGLE scan of array and just two variables for memory).. Does anyone know an answer to this?
Our teachers frequently ask us these sorts of questions... Do you know of any sites having similar questions?
Any help would be appreciated.
Cyanide.
Here''s a possible solution. I only have a basic idea of it, but not all the details. Set both storage variables to the beginning array. One of them will keep moving through the array, and the other holds the value for which no pair has yet been found. There are some problems with this, such as where to increment the comparison variable, but someone else can figure that out.
if u wanted to u could create to 32 bit variables. have one variable store the current position the other now this is the good bit. Use the high order bits of the second variable to stor a single whole number, use the low order bits of the variable to store previous number. would take alot of bit manipulation though
~prevail by daring to fail~
~prevail by daring to fail~
Author
hi,
I found the answer to this one.. it is very simple.
Its that you simply xor each of the previous element to the next element, after xoring the last element of the array the number left is the answer.. the reason I if figured out is that:
2 xor 2 xor 3 is 3, hence..
anyway thanks for the possible solutions
If you know of any other questions like this please post them here too
cyanide.
I found the answer to this one.. it is very simple.
Its that you simply xor each of the previous element to the next element, after xoring the last element of the array the number left is the answer.. the reason I if figured out is that:
2 xor 2 xor 3 is 3, hence..
anyway thanks for the possible solutions
If you know of any other questions like this please post them here too
cyanide.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
