 Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

Easy

None

# PROBLEM:

You are given a binary string S of length N. You can perform the following operation on S:

Pick any set of indices such that no two picked indices are adjacent.
Flip the values at the picked indices (i.e. change 0 to 1 and 1 to 0).

For example, consider the string S = 1101101.
Pick the indices \{1,3,6\}.
Flipping the values at picked indices, we get \underline{1}1\underline{0}11\underline{0}1→0111111.
Note that we cannot pick the set \{2,3,5\} since 2 and 3 are adjacent indices.

Find the minimum number of operations required to convert all the characters of S to 0.

# EXPLANATION:

For each test case we have a binary string of length N.

Now as no adjacent bits can be flipped together. Three cases are possible:

• When the string is already 0, then the number of minimum operations will be zero.
• When no two adjacent bits are set. In this case all the set bits can be converted to 0 in 1 operation.
• When the string contains adjacent set bits. In this case it can be shown that the answer will be 2 since all the odd-indexed set bits and even-indexed set bits can be identified as two different sets.

Evaluating all the above possibilities gives us the result.

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTION:

Time complexity should be O(N) since we have to iterate over the string.

2 Likes

Can anyone suggest me where my code went wrong:

``````#include<bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t--){
int n;
string str;
cin>>n;
cin>>str;
int count = 0;
for(int i=0;i<str.length();i++){
if( str[i] == '1'){
for(int j=i+1;j<str.length();j++){
if( str[j] == '1' and abs(i-j) >= 2){
str[j] = '0';
}
}
count = count+1;
str[i] = '0';
}
}
cout<<count<<endl;
}
return 0;
}
``````

Can anyone help where I am getting wrong. I got 3AC out of 4. but Unable to find where I am getting wrong.

#include<bits/stdc++.h>
using namespace std;
void solve(){
int N;
cin>>N;
string str;
cin>>str;
bool flag1=false,flag2=false;
for(int i=0;i<N-1;++i){
if(str[i]==‘1’ || str[i+1]==‘1’){
flag1=true;
}
if(str[i]==‘1’ and str[i]==str[i+1]){
flag2=true;
}
}
if(!flag1){
cout<<“0”<<"\n";
return;
}
if(!flag2){
cout<<“1”<<"\n";
return;
}
if(flag2){
cout<<“2”<<"\n";
return;
}
}
int main() {
// your code goes here
int T;
cin>>T;
while(T–){
solve();
}
return 0;
}

Corrected in the editorial. Thank you for pointing it out.

1 Like

You are checking the number of 1s only for N-1 characters which fail the test case where we have 1 at the last
eg : 0000001,
Your code will give an output of 0.
Try Debugging this.

Thanks bro.