Binary Base Basics Solution Codechef

by

Table of Contents

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

February Long Challenge 2022 Solution

Leave a Comment

13 − 5 =