I assume that "elements in pairs" means that each value occurs exactly
twice except for the one single.
This algorithm is O(log n) and is nonrecursive. Writing it recursively
would make it a couple of lines shorter, but because it is purely tail
recursion, that is not necessary.
// 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
{
// Pick the midpoint of the array
int midpoint = size/2;
// If we are looking at the second element of a pair, move back
to the first element
if (a[midpoint] == a[midpoint-1]) --midpoint;
// If midpoint is not a pair, that is the single.
else if (a[midpoint] != a[midpoint+1]) return a[midpoint];
// If midpoint is odd, look at left half of the array
if (midpoint % 2) size = midpoint;
else // If midpoint is even, look at the right half of the array
{
a += midpoint;
size -= midpoint;
}
}
}
}
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.
