@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.
