i am having more or less similar code like yours if you get to know where the approach fails please let me know as well.
1
10
0111111000
YES
1 3
But yours return NO
Can anyone give me the testcases as for the testcases tested by me are running fine
please help
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
//int t=1;
while(t–>0)
{
int n=sc.nextInt();
String s=sc.next();
int ceq=1;
int max=0;
int end=0;
int st=0;
int ev=0;
int od=0;
//code for finding biggest consecutive character substring
//and count the no. of 1s and 0s
for(int i=0;i<n-1;i++)
{
if(s.charAt(i)==‘0’)ev++;
if(s.charAt(i)==‘1’)od++;
if(s.charAt(i)==s.charAt(i+1))
{
ceq++;
}
else
{
if(ceq>1)
{
if(ceq>max)
{
max=Math.max(ceq,max);
end=i+1;
st=end-ceq+1;
}
}
ceq=1;
}
}
if(n>1&&s.charAt(n-1)==s.charAt(n-2))
{
if(ceq>max)
{
max=ceq;
end=n;
st=n-ceq+1;
}
}
if(s.charAt(n-1)=='0')
{
ev++;
}
else
{
od++;
}
//that code ended here
int diff=Math.abs(od-ev);
if(n==1)
{
System.out.println("NO");
}
else if(diff==0)
{
System.out.println("YES");
System.out.println(1+" "+n);
}
else if(diff%2==0)
{
System.out.println("YES");
System.out.println(st+" "+(st+(diff/2)-1));
}
else if(diff%2==1)
{
System.out.println("NO");
}
}
}
}
for which testcases my code is failing can someone help me.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
int tt = 1;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
if(n%2!=0){
cout<<"NO"<<'\n';
continue;
}
int cz=0,co=0;
int i=0;
//zero[0]=0;
//one[0]=0;
for(auto &c:s){
if(c=='0'){
cz++;
}else{
co++;
}
}
if(co==cz){
cout<<"YES"<<'\n';
cout<<1<<' '<<n<<'\n';
continue;
}
int diff= n/2-min(co,cz);
int f=0;
int l=0;
int cnt=0;
if(co>cz){
for(int i=0;i<n;i++){
if(s[i]=='1'){
if(cnt==0){
f=i;
}
cnt++;
}else{
cnt=0;
}
if(cnt==diff){
l=i;
break;
}
}
}else{
for(int i=0;i<n;i++){
if(s[i]=='0'){
if(cnt==0){
f=i;
}
cnt++;
}else{
cnt=0;
}
if(cnt==diff){
l=i;
break;
}
}
}
cout<<"YES"<<'\n';
cout<<f+1<<" "<<l+1<<'\n';
}
}
Think of the solution in a way where 0 is treated as -1. Then problem reduces to find an subarray with sum=(number of one-number of zeros)/2
1 Like
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test; cin >> test;
while (test--) {
long long n; cin >> n;
string arr; cin >> arr;
if (n & 1) {
cout << "\nNO";
}
else {
long long count1 = 0, count0 = 0;
for (long long i = 0; i < n; i++) {
if (arr[i] == '1') count1++;
else count0++;
}
if (count1 == count0) {
cout << "\nYES\n" << 1 << " " << n;
}
else if (count0 != count1) {
long long target = n / 2 - min(count0, count1), start = 0, end = 0, count = 0;
char mini = '0';
if (count0 < count1) mini = '1';
for (long long i = 0; i < n; i++) {
if (arr[i] == mini) {
if (count == 0) start = i;
count++;
}
else count = 0;
end = i;
if (count == target) {
cout << "\nYES\n" << start + 1 << " " << end + 1;
break;
}
}
}
}
}
return 0;
}
I want to know the testcase for which my code fails.
Try this test case
n=16
1110111011100111
ANSWER
YES
1 6
N=16
1110111011100111
YES
1 6
1 Like
Hey @subhankar94 
It is not necessary that there is contigious zeros to make no of zero and one equal.
1 Like
it is not always necessary that you will find contiguous zeros or ones so its recommended that you also consider the extra ones or zeros added and convert things accordingly.
below is my code
void solve(){
ll n; cin>>n;
string s; cin>>s;
if(n%2==1){
cout<<“no”<<endl;
return;
}
ll count1=0,count0=0;
for(ll i=0 ; i<n ; i++){
if(s[i]==‘0’) count0++;
else count1++;
}
if(abs(count1-count0)==0){
cout<<“yes”<<endl;
cout<<1<<" “<<n<<endl;
return;
}
if(count0>count1){
ll curr0=0,curr1=0;
ll required1;
for(ll i=0 ; i<n ; i++){
if(s[i]==‘0’) curr0++;
else curr1++;
required1=curr0+count1-(n/2);
if(required1==curr1){
cout<<“yes”<<endl;
cout<<1<<” “<<i+1<<endl;
break;
}
}
}
else{
ll curr0=0,curr1=0;
ll required0;
for(ll i=0 ; i<n ; i++){
if(s[i]==‘0’) curr0++;
else curr1++;
required0=curr1+count0-(n/2);
if(required0==curr0){
cout<<“yes”<<endl;
cout<<1<<” "<<i+1<<endl;
break;
}
}
}
}
hi,
can anyone please point out what is wrong in this code—>
It is written that some possible difference values not all. I hope that helps.
I thought of the same approach during the contest. Later stress tested to find out the test case where my approach was wrong. Take any example like
20
11111011111010111101
Where the consecutive number of ones is just 1 less than the number required to balance the string. In hindsight, it was dumb of me to make that claim.