Hi
The ques explicitly said the elements are in pairs ...But the one given by
sanjay has more than 2 2's ...that question cant be done using bsearch then
On Wed, Aug 24, 2011 at 6:21 PM, Sanjay Rajpal <srn...@gmail.com> wrote:
> 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.
>
--
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.
