Day_079.cpp

/**
 *Problem Statement:    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.If we pick the indices {1,3,6}, 
		then after flipping the values at picked indices, we will get 1?10?110?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.
 *Author: Kunal Kathpal (https://github.com/kunal-2002)
 */
	
#include <bits/stdc++.h>

using namespace std;

int main(){
	cout<<"Enter number of test cases:\t";
	int T,N,i;
	string s;
	cin>>T;
	
	while(T--){
		cin>>N;
		cin>>s;
		for(i=0; i<N; ++i)
			if(s[i]=='1')
				break;
		if(i == N){
			cout<<0<<endl;
			continue;
		}
		else{
			for(i=1;i<N;++i)
				if(s[i] == '1' && s[i-1] == '1')
					break;
			if(i == N)
				cout<<1<<endl;
			else
				cout<<2<<endl;	
		}
		
	}
	return 0;
}