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 <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
