# Any other solution?

#1

Is there any other solution for this problem because I am not understanding the solution given in the editorial.

#2

Just find the subarray with MAX(no.of zeros-no. of ones)

vector Solution::flip(string A) {
vector a;
int ones=0;int zeros=0; int max=INT_MIN;int start=0;int index=0;int ind=0;

``````for(int i=0;A[i]!='\0';i++){
if(A[i]=='0'){
zeros++;
}else{
ones++;
}
if(zeros-ones<0){
start=i+1;
zeros=0;ones=0;
}
//cout<<"zeros "<<zeros<<"ones "<<ones<<endl;
if(max<(zeros-ones)){
max=zeros-ones;
ind=start;
index=i;
}

}
if(max>0){
a.push_back(ind+1);a.push_back(index+1);
}

return a;
``````

}

#3

Just count for number of 1s added (sum++ for addition sum-- for converting existing one in zero).
remember that both the indeces in correct answer would point to zeroes in origional string.

``````vector<int> Solution::flip(string A)
{
int a, b, sum, max, tmp;
sum=max=0;
a=b=tmp=1;
for(int i=0; i<A.size(); i++)
{
if(A[i]=='1')
{
if(!sum)
{
tmp=i+2;
continue;
}
sum--;
}
else if(A[i]=='0')
{
sum++;
if(sum>max)
{
max=sum;
b=i+1;
a=tmp;
}
}
}
if(!max) return {};
return {a, b};
}``````

#4

its simple you have to understand kadane’s algorithm then replace every 1 by -1 and every 0 by 1 and then find the largest possible positive sum and the corrosponding range.
here’s my code
vector Solution::flip(string v) {
int i,n,sum=0,max=INT_MIN,zero0=0,range=0,st=0,f=0,sti=0;
n=v.size();
vector a(n,0);
int temp=0;
vector p;
for(i=0;i<n;i++){
if(v[i]==‘1’){
a[i]=-1;
}
else{

``````        a[i]=1;
}
}
for(i=0;i<n;i++){
sum+=a[i];
//    cout<<"sum is "<<sum<<endl;
if(sum<0){
sum=0;

f=0;
continue;
}
if(a[i]==1){
// one1++;
if(f==0){
st=i;
f=1;
}
}
if(sum>max){
max=sum;
range=i-st+1;
sti=st;
//   cout<<"range is "<<range<<endl;
//   temp=one+one1-zero0;
}
//    cout<<"range is "<<range<<endl;
}
// cout<<"range is "<<range<<endl;
if(max==INT_MIN){
return p;
}
else{
//   cout<<"range is "<<range<<endl;
// cout<<"sti is "<<sti<<endl;
p.push_back(sti+1);
p.push_back(sti+range);
return p;
}
``````

}

#5

vector Solution::flip(string A) {

``````int flg=0;
for(int p=0;p<A.size();p++)
{
if(A[p]=='0')
flg=1;
}
if(flg == 0)
{
vector<int >v;
return v;
}
int mxa=0;
int cc=1;

vector<int >count;
if(A[0]=='0')
count.push_back(0);

for(int i=0;i<A.size()-1;i++)
{
if(A[i] == A[i+1])
cc++;
else
{
count.push_back(cc);
cc=1;
}
}
if(A[A.size()-1] != A[A.size()-2])
count.push_back(1);
else
count.push_back(cc);
``````

// cout<<count.size()<<" nbh"<<endl;
vectorans;

``````int n = count.size();

cc=0;
for(int i=0;i<n;i++)
{
if(i%2 == 0)
{
cc-=count[i];
cc=max(cc,0);
}
else
{
cc+=count[i];
}
mxa=max(mxa,cc);
}
//cout<<mxa<<endl;
``````

/* for(int i=0;i<count.size();i++)
cout<<count[i]<<" ";
cout<<endl;*/

``````int indicator=0;
int maxaa=-1;
int i;
cc=0;
for( i=0;i<n;i++)
{
if(i%2 == 0)
{
cc-=count[i];
}
else
{
cc+=count[i];
}
maxaa=max(maxaa,cc);
cc=max(cc,0);

indicator += count[i];
if(maxaa == mxa)
break;
}
``````

/* cout<<“tgt”<<endl;
cout<<indicator<<endl;
cout<<“fjfkf”<<endl;*/
int right = indicator ;
cc =0;
int left;
//cout<<right<<"-=-="<<endl;
for(i = right-1;i>=0;i–)
{
if(A[i] == ‘0’)
cc++;
else
cc–;

``````    if(cc == mxa)
left = i+1;

}
``````

// int left = indicator+1 ;
//cout<<left<<" "<<right<<endl;
if(right >=0 && left>=0)
{
ans.push_back(left);
ans.push_back(right);
return ans;
}
return ans;

}