After working on it quite a bit I got an O(log n) algorithm working.
For small cases (size < 10) it sequentially finds the solution.
For larger cases it uses a binary search:
Starting at the midpoint, find the left and the right ends of the
region with values equal to the value at the midpoint. This is done by
another binary search. That gives three regions:
1. Values less than the midpoint value in the left part of the array
2. Values equal to the midpoint value
3. Values greater than the midpoint value in the right part of the
array
One of those regions will be odd in size. If it is region 2, the
midpoint value is the repeated value. Otherwise, narrow the search to
the odd-sized region.
In 1000 trials on an array of size 1001 including a variety of input
data/different sized clumps of equal values, it took on average 7.5
iterations through the main loop and 14 iterations through the inner
binary search loop per call.
Code follows (apologies for how cutting and pasting messes up the
formatting):
// Find left edge of group of equal values including a[midpoint]
int findLeftEdge(int *a, int midpoint)
{
// We know that midpoint > 3. For a small case, just search
sequentially.
if (a[midpoint-4] != a[midpoint])
{
while(a[midpoint-1] == a[midpoint])
--midpoint;
return midpoint;
}
int min = 1; // findSingle eliminates cases where a[0] ==
a[midpoint]
int max = midpoint-4; // Covered by first check above
while(1)
{
int median = (min + max) / 2;
if (a[median] == a[midpoint])
{
if (a[median-1] != a[midpoint]) return median;
max = median-1;
}
else
{
if (a[median+1] == a[midpoint]) return median+1;
min = median+1;
}
}
}
// FInd right edge of group of equal values including a[midpoint]
int findRightEdge(int *a, int midpoint, int size)
{
if (a[midpoint+4] != a[midpoint])
{
while(a[midpoint+1] == a[midpoint])
++midpoint;
return midpoint;
}
int min = midpoint + 4;
int max = size-2;
while(1)
{
int median = (min + max) / 2;
if (a[median] == a[midpoint])
{
if (a[median+1] != a[midpoint]) return median;
min = median + 1;
}
else
{
if (a[median-1] == a[midpoint]) return median-1;
max = median-1;
}
}
}
// Given an array "a" of size elements in which all elements occur in
pairs except for one single item,
// find the single item and return its value.
int findSingle(int *a, int size)
{
while(1)
{
// For an array of size 1, the only element is the single.
if (size == 1) return a[0];
// The logic below won't work for size three, but it is simple to
find the single.
else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0];
else if (size < 10)
{
int result = a[0];
for(int i = 1; i < size; ++i)
result ^= a[i];
return result;
}
else
{
// Pick the midpoint of the array
int midpoint = size/2;
// If all values to the left of midpoint are equal, singleton must
be to right.
if (a[midpoint] == a[0])
{
a += midpoint;
size -= midpoint;
if ((size%2) == 0)
{
++a;
--size;
}
}
// If all values to the right of midpoint are equal, singleton must
be to left.
else if (a[midpoint] == a[size-1])
{
size = midpoint;
if ((size%2) == 0) --size;
}
else
{
int left = findLeftEdge(a,midpoint);
int right = findRightEdge(a,midpoint,size);
if ((right-left) % 2 == 0) return a[midpoint];
if (left % 2) size = left;
else
{
++right;
a += right;
size -= right;
}
}
}
}
}
On Aug 24, 4:49 am, atul purohit <[email protected]> wrote:
> Hi,
>
> A* sorted *integer array contains elements in pairs. All the pairs are
> complete except one element whose pair is missing. Find that element.
>
> Ex. { 1,1,2,2,2,2,3,3,4,5,5}
> result = 5
>
> There is a standard solution which returns an XOR of all the elements. But
> this needs O(n) time complexity. The person who asked me this question said
> that this can be done in < O(n). Maybe we can eliminate some elements.
> Anyone knows how to do this?
>
> Cheers,
> Atul
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
