See interviewer said that it can be done in <O(n) and also only *ONE* pair
is missing i have two approaches
1st approach
check 1st element say n= arr[0] // i=0
now in the for() loop increment i by 2 // i=2
check if arr[i-1]==n? if no, answer is n else n=arr[i] and repeat the same
with i+=2;
2nd approach O(log(n))
do binany search
if suppose upto ith position all elements are in pairs then if 'i' is even
then arr[i]==arr[i+1] else if 'i' is odd then arr[i]==arr[i-1] mean mismatch
is on right side
if above conditions does not met mean upto ith position there is mismatch
so search left side
if arr[i]!=arr[i+1] and arr[i]!=arr[i-1] hence desire o/p if arr[i] ...
i hope i m clear.....
On Wed, Aug 24, 2011 at 10:08 PM, Ankur Garg <ankurga...@gmail.com> wrote:
> 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.
>
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
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.
