hmm the problem is we need O(1) space....having that count wont make it
O(1).
i had an approach in mind of O(n) time and O(1) space..problem is i havent
tested/debugged the code but it is O(1) space i guess and O(n) time.
if total number of zeros(M) and 1s(N) are same print the whole array
else
the logic i used is something like this...
1)traverse the array from 0 to n
2)2 pointers , one pointing to the first 0 and other pointing to the first 1
in the array
3)i and j are 2 variables to keep count of 0 and 1 that we have seen so far
as we keep traversing
4) 2 more varibales are used to maintain count of left over 0s and 1s from
our current position( we know the total number of zeros and ones in O(n))
5)if at any point i is equal to j and either left over 0s or 1s is 0 then
print array from lesser of pointer index(lesser means one of the pointers is
behind the other) till current index we are looking at
the prtining from lesser pointer index till current index is if only none of
the pointers have been changed in the process in between
6) in case i or j becomes greater than N or M repsectively
i do some steps with pointer updation...i am just posting the code....maybe
u can check and see if it is logically ok..it hasnt been tested....
M is number of zerso in array
N is number of ones in array
ptri=pointer to array
ptrj=pointer to array
i and j hold count of 0 and 1 respectively as i move along array
M is number of zeros N is number of ones in the array ..u can find this in
O(n)..if they are equal print whole array
else
chnagei=0;
changej=0;
ptri=null
ptrj=null;
done0=0;
done1=0;
savestart=null
saveend=Null;
for(int index=0;index<n;index++)
{
if(a[index]==0 && done0 ==0)
{
ptri=a+index;
done0++;
}
if(a[index]==1 && done1 ==0)
{
ptrj=a+index;
done1++;
}
if(a[index]==0)
i++;
if(a[index]==1)
j++;
lefti=M-i; //number of 0s left in array
leftj=N-j; //number of 1 left in array
if((lefti==0 || leftj==0 )&&(i==j))
{
if(changei==0 && chnagej==0)
{
if(ptri<ptrj)
{
savestart=ptri;
saveend=a+index;
break;
}
else
{
savestart=ptrj;
saveend=a+index;
break;
}
}
else
{
if(i==j)
{
if(ptri<ptrj)
{
savestart=ptrj;
saveend=a+index;
}
else
{
savestart=ptri;
saveend=a+index;
}//end of if
}
}//end of else
}
lefti=M-i;
leftj=N-j;
if(i>N)
{
ptri=ptri+(N-i)
changei=1;
i=i-(N-i);
if(j!=0 && i>N-j)
{
j=0;
N--;
}
}
if(j>M)
{
ptrj=ptrj+(M-j);
changej=1;
j=j-(M-j);
if(i!=0 && j>M-i)
{
i=0;
M--;
}
}
}
print from save start to save end..that is answer
On Fri, Aug 5, 2011 at 1:09 PM, surender sanke <surend...@gmail.com> wrote:
> Hi,
>
> for 1 do +1
> for 0 do -1
> maintain count at every index of array
> eg: 1000000110
> array X 1 0 0 0 0 0 0 1 1 0
> count 0 1 0 -1 -2 -3 -4 -5 -4 -3 -4
> index -1 0 1 2 3 4 5 6 7 8 9
>
> find count with same value having max index difference.
> -3 is count at index 4 and 8
> max difference is 8-4 = 4
> -4 is count at index 5 and 9
> max difference is 9-5 = 4
> to reduce traverse time after count calculation
> take a map<count,<i,j>>;
> i - first index of array having same count,
> j - last index of array having same count
> as and when u encounter count create map value with i
> else if already exist update j, and update max with MAX(j-i,max)
>
> Surender
>
> On Fri, Aug 5, 2011 at 2:25 PM, Arun Vishwanathan <
> aaron.nar...@gmail.com> wrote:
>
>>
>> by the way doesnt it look like an O(n^2) algo?
>>
>> On Fri, Aug 5, 2011 at 10:53 AM, Arun Vishwanathan <
>> aaron.nar...@gmail.com> wrote:
>>
>>>
>>> would u mind giving a short explanation of yr code too if possible?
>>>
>>>
>>> On Thu, Aug 4, 2011 at 5:38 PM, Apoorve Mohan <apoorvemo...@gmail.com>wrote:
>>>
>>>> I think this should work....tell me if this works...
>>>>
>>>> void longest_0_1_substring(char *str)
>>>> {
>>>> int size=0,count=0,max=0,pos=0,prev=0,prev_pos=0,ptr=0,i=0,j=0;
>>>>
>>>> while(*str++)
>>>> size++;
>>>> str -= (size + 1);
>>>>
>>>> while(i<size)
>>>> {
>>>> for(j=i;(j < size) && (str[j]==str[j+1]);++j)
>>>> count++;
>>>> count++;
>>>> if(ptr > 1)
>>>> {
>>>> if(count >= prev)
>>>> {
>>>> if(prev > max)
>>>> {
>>>> max = prev;
>>>> pos = prev_pos;
>>>> }
>>>> }
>>>> else
>>>> {
>>>> if(count > max)
>>>> {
>>>> max = count;
>>>> pos = i - prev;
>>>> }
>>>> }
>>>> }
>>>> prev = count;
>>>> prev_pos = i;
>>>> i += count;
>>>> ++ptr;
>>>> count = 0;
>>>> }
>>>>
>>>> printf("substring starts at position %d and is of size %d
>>>> .",pos,max);
>>>>
>>>>
>>>>
>>>> }
>>>>
>>>> On Thu, Aug 4, 2011 at 6:25 PM, himanshu kansal <
>>>> himanshukansal...@gmail.com> wrote:
>>>>
>>>>> okie...can someone do it in O(n) space...bt time shld be linear
>>>>> only....
>>>>>
>>>>>
>>>>> On Thu, Aug 4, 2011 at 2:13 AM, Prakash D <cegprak...@gmail.com>wrote:
>>>>>
>>>>>> O(1) space is toooo hard for this task
>>>>>>
>>>>>>
>>>>>> On Thu, Aug 4, 2011 at 12:55 AM, payel roy <smithpa...@gmail.com>wrote:
>>>>>>
>>>>>>> Is there any solution for the above?
>>>>>>>
>>>>>>>
>>>>>>> On 3 August 2011 21:09, coder coder <i.code.program...@gmail.com>wrote:
>>>>>>>
>>>>>>>> ya amazon will be visiting our campus within few days
>>>>>>>>
>>>>>>>> --
>>>>>>>> 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
>>>>> Himanshu Kansal
>>>>> Msc Comp. sc.
>>>>> (University of Delhi)
>>>>>
>>>>>
>>>>> --
>>>>> 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
>>>>
>>>> Apoorve Mohan
>>>>
>>>>
>>>> --
>>>> 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.
