yes this is the only one till now, but i think we can do better also. Hope a better solution will be posted by someone soon.
Sanju :) On Wed, Aug 24, 2011 at 5:22 AM, Venkat <venkataharishan...@gmail.com>wrote: > @Sanju: For your input both above solution wont work... > > Do you ve any soultion for your input?? > For your input.... Xor all numbers - will give you the result....:) > but its O(n) > > Anyway your input allow everyone to think little wider than Binay > search. > > > Thanks > Venkat > > > On Aug 24, 4:05 pm, Sanjay Rajpal <srn...@gmail.com> wrote: > > @Venkat : suppose if the array were : 1 2 2 2 2 2 2 2 2 2 2, would ur > > solution work ? > > > > Sanju > > :) > > > > On Wed, Aug 24, 2011 at 3:58 AM, Ankit Minglani < > ankit.mingl...@gmail.com>wrote: > > > > > > > > > > > > > > > > > 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. > > -- > 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.