XOR all the elements, the answer is the number you want.
On Aug 24, 5:11 pm, Don <dondod...@gmail.com> wrote:
> 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.
