Page Contents
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
- Random OR Solution Codechef
- Digit Multiplication By K Solution Codechef
- Remove Adjacent Solution Codechef
- Bitwise Blend Solution Codechef
- Binary Base Basics Solution Codechef
- N Queens Puzzle Solved ! Solution Codechef
- Chef and the Hair Salon Solution Codechef
January Long Challenge 2022 Solution
- TCS Examination EXAMTIME Solution Codechef
- Chef and Fixed Deposits MINFD Solution Codechef
- Crying Colours CRYCOLR Solution Codechef
- Power Sum POWSUM Solution Codechef
- Sum and OR SUMANDOR Solution Codechef
- Tree Master TRMT Solution Codechef
- Array Partition ARRPART Solution Codechef
- Keplers Law KEPLERSLAW Solution
- Covid Spread COVSPRD Solution
- Prime in a binary string PINBS Solution
- Retrieve back the Array XORED Solution
- Chef and Riffles RIFFLES Solution
- Sequence Master MASTER Solution
- Generating Cycles GENECYC Solution