mine approach is log(n)
check it out first
On Thu, Aug 25, 2011 at 1:21 AM, Don <dondod...@gmail.com> wrote:
> 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.
>
>
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
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.
