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