I'm going to assume that "elements in pairs" means exactly two of each
element except for the one which is missing it's pair.
The recursive solution is simple, but it only uses tail recursion, so
it is worthwhile to do it iteratively.
int findSingle(int *a, int size)
{
int result;
while(1)
{
printf("a[0] = %d size=%d\n", a[0], size);
if (size == 1)
{
result = a[0];
break;
}
else if (size == 3)
{
result = (a[0] == a[1]) ? a[2] : a[0];
break;
}
else
{
int midpoint = size/2;
if (a[midpoint] == a[midpoint-1]) --midpoint;
if (a[midpoint] != a[midpoint+1])
{
result = a[midpoint];
break;
}
else if (midpoint % 2)
{
size = midpoint;
}
else
{
a += midpoint;
size -= midpoint;
}
}
}
return result;
}
On Aug 24, 4:49 am, atul purohit <gonewiththe...@gmail.com> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
