How about this :
We use a divide and conquer approach and since the array is sorted.
We find the middle element and check its value with its immediate left and
right element .. it must match with anyone of them ..
if it doesnt we have found such a element . and otherwise we divide the
array again ..
and then again find the middle element .. to check the same condition ..
This will take O(lg n ) time :)
On Wed, Aug 24, 2011 at 3:45 PM, Venkat <venkataharishan...@gmail.com>wrote:
> we can solve this with the help of binary search.
>
> we know N, which is odd(because of one pair missing)
>
> We divide it array. Let consider your input { 1,1,2,2,2,2,3,3,4,5,5}
>
> int find_culprit(int[] array, int start, int end)
> {
> if(end==start)
> return -1;
>
> int mid=((end-start) / 2) + start;
> if array[mid] == array[mid-1]
> return find_culprit(mid,end)
> if(array[mid] == array [mid +1]
> return find_culprit(start, mid);
> else
> return array[mid];
> }
>
> Run through:
> Steps1: find_culprit(array,0,8)
> mid=4
> Step 2 : find_culprit(array,4,8))
> mid=6
> step 3 : find_culprit(array,6,8))
> mid=7
> return array[7]=4 (which dont have pair)
>
>
> Run time O(log n+1) = O(log n)
>
> Please ask if you ve any doubts.....
>
> Regards
> Venkat.
>
> On Aug 24, 2:49 pm, 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.
>
>
--
The more you sweat in the field, the less you bleed in war."
Ankit Minglani
NITK Surathkal
--
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.
