{ 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also
comes under this problem?
surender
On Thu, Aug 25, 2011 at 8:12 AM, Dave <dave_and_da...@juno.com> wrote:
> @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.
>
>
--
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.
