# Binary Base Basics Solution Codechef

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

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;
}
}``````