Binary Base Basics Solution Codechef
You are given a binary string S and an integer K. In one operation, you can pick any bit and flip it, i.e turn 0 to 1 or 1 to 0. Can you make the string S a palindrome using exactly K operations?
Print YES
if this is possible, and NO
if it is not.
Input Format
- The first line of input contains one integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of two lines of input.
- The first line of each test case contains two space-separated integers N and K, denoting the length of the binary string and the number of operations to be performed.
- The second line contains the binary string S.
Output Format
For each test case, print the answer on a new line — YES
if the S can be made a palindrome using exactly K operations, and NO
otherwise.
You may print each character of YES
and NO
in either uppercase or lowercase (for example, yes
, yEs
, Yes
will all be considered identical).
Constraints
- 1≤T≤1000
- 1≤N≤1000
- 0≤K≤N
- S is a binary string, i.e, contains only characters 0 and 1
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
2
3 0
110
6 1
101100
Sample Output 1
NO
YES
Explanation
Test case 1: S is not a palindrome, and no operations can be performed on it because K=0.
Test case 2: Flip the first bit to obtain S=001100, which is a palindrome.
SOLUTION
Program: Binary Base Basics Solution Codechef in Python
for _ in range(int(input())):
n,k=map(int,input().split())
s=input()
p=0
for i in range(n//2):
if s[i]!=s[n-i-1]:
p+=1
c=k-p
if(c>=0 and c%2==0) or (c>=0 and n%2==1):
print('yes')
else:
print('no')
Program: Binary Base Basics Solution Codechef in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;cin>>t;
while(t--)
{
int n, k;
cin>>n>>k;
string s;
cin>>s;
int i = 0, j = n-1;
int operation = 0;
while(i <= j)
{
if(s[i] != s[j])
operation++;
i++;j--;
}
if(operation <= k)
{
if((k-operation) % 2 == 0)
cout<<"YES"<<endl;
else if(n%2 != 0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
else
cout<<"NO"<<endl;
}
return 0;
}
Program: Binary Base Basics Solution Codechef in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i=0;i<T;i++){
int N = sc.nextInt();
int K = sc.nextInt();
sc.nextLine();
String str = sc.nextLine();
boolean result = isPossible(N,K,str);
System.out.println(result?"YES":"NO");
}
}
public static boolean isPossible(int N,int K,String str){
for(int i=0;i<N/2;i++){
if(str.charAt(i)!=str.charAt(N-1-i)){
K--;
if(K<0){
break;
}
}
}
boolean flag = K>=0;
if(flag){
if(K%2==1){
flag=(N%2)==1;
}else{
flag=true;
}
}
return flag;
}
}