Binary Base Basics Solution Codechef

by

Binary Base Basics Solution Codechef

You are given a binary string SS and an integer KK. In one operation, you can pick any bit and flip it, i.e turn 00 to 11 or 11 to 00. Can you make the string SS a palindrome using exactly KK operations?

Print YES if this is possible, and NO if it is not.

Input Format

  • The first line of input contains one integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of two lines of input.
    • The first line of each test case contains two space-separated integers NN and KK, denoting the length of the binary string and the number of operations to be performed.
    • The second line contains the binary string SS.

Output Format

For each test case, print the answer on a new line — YES if the SS can be made a palindrome using exactly KK 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≤10001≤T≤1000
  • 1≤N≤10001≤N≤1000
  • 0≤K≤N0≤K≤N
  • SS is a binary string, i.e, contains only characters 00 and 11

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 11: SS is not a palindrome, and no operations can be performed on it because K=0K=0.

Test case 22: Flip the first bit to obtain S=001100S=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;
	}
}

February Long Challenge 2022 Solution

January Long Challenge 2022 Solution

Leave a Comment

twenty + eight =