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.