×

LONGSEQ - Editorial

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

Cakewalk

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.

This question is marked "community wiki".

6★djdolls
2.2k518484
accept rate: 0%

19.8k350498541

 0 Another similar method could be just to count the number of ones or zeros and check whether its value is $1$ or $length - 1$. answered 16 Sep '16, 13:53 321●1●8 accept rate: 8%
 0 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 answered 06 Nov '16, 21:18 1 accept rate: 0%

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&lt;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?

1
accept rate: 0%

#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(nombresizeof(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.

2★magmine
1
accept rate: 0%

 0 This may never be answered but i don't get why abs(num_zeros - num_ones) == 1 ? "Yes":"No" doesn't work!?! answered 04 Oct '17, 02:13 0★uxxi 1 accept rate: 0%
 0 Where am I wrong? #include #include #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; i1) { flag=1; break; } } if(flag==0) { if(min(o,z)!=0) cout<<"Yes"<
 0 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. answered 04 Feb '18, 14:49 2★handra 1 accept rate: 0%
 0 can someone tell me why my c++ code is not working... thanks a lot https://ideone.com/7dI5qm answered 30 May '18, 13:33 0●1 accept rate: 0%

include <string>

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??

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,652
×947
×643
×129
×5

question asked: 15 Sep '16, 14:47

question was seen: 4,818 times

last updated: 15 Aug '18, 10:01