LONGSEQ - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Praveen Dhinwa
Editorialist: Ajay K. Verma

DIFFICULTY:

Cakewalk

PREREQUISITES:

Ad-hoc, String

PROBLEM:

Given a binary string, find if it is possible to make all its digits equal by flipping exactly one digit.

QUICK EXPLANATION:

All the digits of the binary string can be made equal by flipping exactly one digit if and only if the original string has exactly one digit equal to zero, or exactly one digit equal to one.

EXPLANATION:

Suppose that the input string has exactly one digit equal to one, and all other digits are zero, then we can flip this digit, which will result in a string with all digits equal to zero. Similarly, if the input string has exactly one digit equal to zero, and all other digits are one, then flipping this digit would result in a string with all digits equal to one.

On the other hand, if all digits of a string can be made identical by doing exactly one flip, that means the string has all its digits equal to one another except this one digit which has to be flipped, and this digit must be different than all other digits of the string. The value of this digit could be either zero or one. Hence, this string will either have exactly one digit equal to zero, and all other digits equal to one, or exactly one digit equal to one, and all other digit equal to zero.

Therefore, we only need to check whether the string has exactly one digit equal to zero/one, and if so, the answer is yes; otherwise the answer is no.

void f(string str) {
  int num_zeros = 0;
  int num_ones = 0;

  for (char ch : str) {
    if (ch == '0') {
      ++num_zeros;
    } else {
       ++num_ones;
    }
  }

  if (num_zeros == 1 || num_ones == 1) {
    print("Yes\n");
  } else {
    print("No\n");
  }
}

TIME COMPLEXITY:

O (N), where N is the length of the string.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be uploaded soon.
Tester’s solution will be uploaded soon.

2

Another similar method could be just to count the number of ones or zeros and check whether its value is 1 or length - 1.

3

no_input=input()
yn_array=[]
for i in xrange(0,no_input):
take_number=raw_input()
new_array=list(take_number)
new_array=map(int,new_array)
new_array.sort()
if new_array==[0] or new_array==[1]:
message=“No”
elif new_array[0]==0 and new_array[1]==1:
message=“Yes”
elif new_array[1]==0:
message=“No”
elif new_array[0]==1:
message=“No”
else:
message=“Yes”
yn_array.append(message)
for i in xrange(len(yn_array)):
print yn_array[i]
This is the solution I wrote in Python. It returns WA. I can’t figure out what is the problem. Also I have difficulty understanding C code. Thanks

4

#include<stdio.h>
main()
{
int t,i;
scanf("%1d",&t);
int a[t];
for(i=0;i<t;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<t;i++)
{
int x=a[i];
int p=0,f=0;
while(x>0)
{
int d=x%10;
if(d==0)
p++;
else if(d==1)
f++;
x=x/10;
}
if(p==1||f==1)
printf(“yes\n”);
else
printf(“no\n”);
}
}
why can’t this be the solution to your question?

5

#include<stdio.h>
#include<stdlib.h>

int inv(int n){
int i=1,k=10,ordre,s=0,m=1,r=0;
//k=puissances de 10;i= compteur; s= somme partiel;
int compt=1,p=1,j=0,S=0;//S=total sum ; p =puissances de 10; j=compter
int t[18];//tableau qui stockera les chiffres de n;

while(((float)(n/k)>=1){//On calcule k tq k=10 o;
	k=k*10;
}
k=k/10;
ordre=k;
//printf("ordre=%d\n",ordre);
while(k!=1){
	k=k/10;
	m++;
}
//printf("m=%d\n",m);
k=ordre;
do{
	for(i=1;i<10;i++){ //on determine la chiffre de la dizaine,centaine...etc
			if(((float)(n/(S+k*i)))<1){
			break;
		}
		
	}
	t[compt-1]=i-1;//on emmagazine la chiffre
	k=k/10;//on réduit la puissance de k;
	//printf("k=%d\n",k);
	do{
		s=s+t[j]*(ordre/p);//on calcule la somme partielle;
		j++;
		p=p*10;
	}while(j<compt);
	r=j;
	//printf("r=%d ",r);
	S=s;
	//printf("S=%d\n",S);
	s=0;
	i=1;
	j=0;
	p=1;
	compt++;
}while(r!=m);
/*for(i=0;i<compt-1;i++){
	printf("t= %d ",t[i]);
}*/

j=0;s=0; //printf("\n");
for(i=0;i<compt-1;i++){
	if(t[i]==0){
		j++;
	}
}
i=0;
for(i=0;i<compt-1;i++){
	if(t[i]==1){
		s++;
	}
}
if(s==1 && j>=1 ) printf("Yes\n");
else if(j==1 && s>=1) printf("Yes\n");
else if(s==0 && j>1){
	printf("No\n");
}else if(j==0 && s>1) printf("No\n");
else if(s>1 || j>1){
	printf("No\n");
}

}
main(){
int * tab;
int nombre;
int i;
scanf("%d",&nombre);
tab=(int*)malloc(nombre*sizeof(int));
for(i=0;i<nombre;i++){
scanf("%d",&tab[i]);
}
for(i=0;i<nombre;i++){
inv(tab[i]);
}
free(tab);
}
it works for me but when I submit the code in codechef the answer is wrong I don’t now why ? btw the code is in C.

6

This may never be answered but i don’t get why abs(num_zeros - num_ones) == 1 ? "Yes":"No" doesn’t work!?!

7

Where am I wrong?
#include
#include<string.h>
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
string no;
cin>>no;
int o=0, z=0, flag=0;
for(int i=0; i<no.length(); ++i)
{
if(no[i]==‘1’)
o++;
else
z++;
if(min(o,z)>1)
{
flag=1;
break;
}
}
if(flag==0)
{
if(min(o,z)!=0)
cout<<“Yes”<<endl;
else
cout<<“No”<<endl;
}
else
cout<<“No”<<endl;
}
}

8

This may never be answered but i don’t
get why abs(num_zeros - num_ones) == 1
? “Yes”:“No” doesn’t work!?!

Let’s assume num_zeros = 10 and num_ones = 1. Based on the test case criteria, this should be answered with Yes. However, using abs ( num_zeros - num_ones ) == 1 yields to abs ( 10 - 1 ) == 1 which result in 9 == 1 comparison (this is FALSE), hence you will print No.

9

can someone tell me why my c++ code is not working…
thanks a lot

10

#include
#include
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
string c;
cin>>c;
long flag_1=0, flag_0=0;
for(long i=0; i<c.length(); i++)
{
if(c[i]==‘1’)
{
flag_1++;
}
else if(c[i]==‘0’)
{
flag_0++;
}

    }
    if(flag_1>=1 && flag_0==1)
    {
        cout<<"Yes"<<endl;
    }
    else if(flag_0>=1 && flag_1==1)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }

}

}

I don’t understand why this isn’t working.Can someone help??