@Shailesh: Sir, your response is unresponsive, because the original
poster specifically asked for a solution that was < O(n). Please don't
waste our time giving answers that so obviously do not meet the
problem statement.
Dave
On Aug 24, 6:33 pm, smb <shaileshbir...@gmail.com> wrote:
> 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- Hide quoted text -
>
> - Show quoted text -
--
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.
