#include<stdio.h>
#define n 11
int main()
{
int ar[n]={1,0,1,1,1,0,0,0,0,0,1};
int a[n][n];
int l,i,k,maxlength=0,start,end;
for(i=0;i<n;i++)
{
ar[i]==0?(a[i][i]=-1):(a[i][i]=1);
}
for(l=2;l<=n;l++)
{
for(i=0;i<=n-l;i++)
{
for(k=i;k<i+l-1;k++)
{
a[i][i+l-1]=a[i][k]+a[k+1][i+l-1];
if(a[i][i+l-1]==0 && l>maxlength)
{
maxlength=l;
start=i;
end=i+l-1;
}
}
}
}
printf("maxm length=%d\n",maxlength);
for(i=start;i<=end;i++)
printf("%d ",ar[i]);
}
On Tue, Jul 5, 2011 at 11:49 AM, Kunal Patil <[email protected]> wrote:
> @Sunny : Excellent !!! Keep posting such nice solutions !! :)
>
>
> On Sat, Jul 2, 2011 at 1:47 AM, Anika Jain <[email protected]> wrote:
>
>> ohh ok i got it.. thanx :)
>>
>>
>> On Sat, Jul 2, 2011 at 12:48 AM, sunny agrawal
>> <[email protected]>wrote:
>>
>>> it is (2,4] not [2,4].
>>> open interval, close interval ......... consider (i,j] as [i+1,j]
>>>
>>> because a[i] = sum of values from 0 to i
>>> and a[j] = sum of values from 0 to j
>>> if a[i] = a[j] then it means sum does not changes between a[i] to a[j]
>>>
>>> so from i+1 to j there are equal no of 1's and -1's
>>> or in other words equal no of 0's and 1's
>>>
>>>
>>> On Sat, Jul 2, 2011 at 12:42 AM, Anika Jain <[email protected]>wrote:
>>>
>>>> @sunny: in a[2,4] has 2 1s and one 0 then how is it a solution? i mean i
>>>> didnt get wen a[i]==a[j] then a[i,j] is a solution case..
>>>>
>>>> On Fri, Jul 1, 2011 at 4:13 PM, sunny agrawal
>>>> <[email protected]>wrote:
>>>>
>>>>> Take an array of size of the length of the string.
>>>>> fill the array positions with one where string contains 1, and -1 where
>>>>> it is 0
>>>>>
>>>>> Now for each i (1,n-1) perform the following operation
>>>>> a[i] = a[i-1] + a[i]
>>>>> now a[i] will contains sum of values from a[0] to a[i] in original
>>>>> array.
>>>>>
>>>>> Now only thing remains to find is two indexes in this array such that
>>>>> a[i] = a[j]
>>>>> where ever this condition is met ( i,j ] is a solution
>>>>>
>>>>> or if for some i a[i] = 0 in this case [0,i] will be a solution
>>>>>
>>>>> this can be done using hashing
>>>>> hash the values in the array of size 2*n+1. as range of values is -n to
>>>>> n and keep track of max interval.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Fri, Jul 1, 2011 at 3:22 PM, Anantha Krishnan <
>>>>> [email protected]> wrote:
>>>>>
>>>>>> Given a string containing 0's and 1's. One would need to find the
>>>>>> longest sub-string such that the count of 0's is equal to the count of
>>>>>> 1's
>>>>>> in the largest sub string.
>>>>>>
>>>>>> Regards
>>>>>> Anantha Krishnan
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to [email protected].
>>>>>> To unsubscribe from this group, send email to
>>>>>> [email protected].
>>>>>> For more options, visit this group at
>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Sunny Aggrawal
>>>>> B-Tech IV year,CSI
>>>>> Indian Institute Of Technology,Roorkee
>>>>>
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected].
>>>>> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> Sunny Aggrawal
>>> B-Tech IV year,CSI
>>> Indian Institute Of Technology,Roorkee
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
