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.
