You are not logged in. Please login at www.codechef.com to post your questions!

×

LONGSEQ - Editorial

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.

This question is marked "community wiki".

asked 15 Sep '16, 14:47

djdolls's gravatar image

6★djdolls
2.2k518484
accept rate: 0%

edited 16 Sep '16, 12:57

admin's gravatar image

0★admin ♦♦
19.7k350498541


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

link

answered 16 Sep '16, 13:53

rishabh.jain9196's gravatar image

4★rishabh.jain9196
32118
accept rate: 8%

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

link

answered 06 Nov '16, 21:18

noobcoder5's gravatar image

0★noobcoder5
1
accept rate: 0%

edited 06 Nov '16, 21:19

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?

link

answered 22 Jan '17, 08:29

quantum_007's gravatar image

1★quantum_007
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.

link

answered 20 Feb '17, 00:48

magmine's gravatar image

2★magmine
1
accept rate: 0%

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

link

answered 04 Oct '17, 02:13

uxxi's gravatar image

0★uxxi
1
accept rate: 0%

Where am I wrong? #include<iostream> #include<string.h> #include<algorithm> 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; } }

link

answered 19 Oct '17, 16:43

rajdipsaha's gravatar image

1★rajdipsaha
1
accept rate: 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.

link

answered 04 Feb '18, 14:49

handra's gravatar image

2★handra
1
accept rate: 0%

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

https://ideone.com/7dI5qm

link

answered 30 May '18, 13:33

bipul1895's gravatar image

3★bipul1895
01
accept rate: 0%

include <iostream>

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

link

answered 15 Aug '18, 10:01

apoorv_01's gravatar image

2★apoorv_01
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,482
×1,600
×921
×630
×129
×5

question asked: 15 Sep '16, 14:47

question was seen: 4,684 times

last updated: 15 Aug '18, 10:01