304 North Cardinal St.
Dorchester Center, MA 02124

# Binary Substitution CodeChef Solution

## Problem – Binary Substitution CodeChef Solution

Chef has binary string S of length N.

Chef can perform the following operation on the string:

• Choose a contiguous subarray SL​,SL+1​,…,SR​ such that the count of set bits in the subarray is equal to the count of unset bits in the subarray.
• Replace the chosen subarray with either a set bit or an unset bit.

Chef wants to reduce the string to minimum possible length using minimum number of given operations. Help Chef by telling him the minimum length and also the operations required to obtain that. If there are multiple ways to obtain the answer, print any.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first line of each test case contains a single integer N, denoting the length of the binary string.
• The second line of each test case contains a binary string S.

### Output Format

For each test case, output K+1 lines:

• The first line should contain two space-separated integers M and K, denoting the minimum length that can be obtained and the minimum number of operations required to obtain it respectively.
• Then, K lines follow, where the i^th line denotes the i^th operation:
• Each operation is denoted using three space separated integers LR, and B.
The integers L and R denote the chosen substring such that (1≤L<R≤∣S∣) and the substring S[L,R] has equal count of set and unset bits. Note that, |S| denotes the length of the current string.
The integer B denotes the bit with which the substring is replaced.

• 1≤T≤100
• 1≤N≤1000

### Sample 1:

``````Input:
3
4
1100
1
1
5
11000
Output:
1 1
1 4 0
1 0
1 2
1 4 1
1 2 1
``````

### Explanation:

Test case 1: We can reduce the string to a string of length 1. We require only 1 operation to do so:

• Choose L=1,R=4, and B=0. We chose the substring S[1,4] which contains 2 set bits and 2 unset bits. We can replace the chosen substring with bit 0.

Test case 2: The given string is of length 1. Thus, we cannot reduce it any further.

Test case 3: We can reduce the string to a string of length 1. We require 2 operations to do so:

• Operation 1: Choose L=1,R=4, and B=1. We chose the substring S[1,4] which contains 2 set bits and 2 unset bits. We can replace the chosen substring with bit 1. Thus, the string after this operation is S=10.
• Operation 2: Choose L=1,R=2, and B=1. We chose the substring S[1,2] which contains 1 set bit and 1 unset bit. We can replace the chosen substring with bit 1. Thus, the string after this operation is S=1.

## Binary Substitution CodeChef Solution in C++14

``````#include<bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define maxv 9223372036854775807
#define minv -9223372036854775808
#define int long long

int mod = (int)1e9+7;
using namespace std;

// Tips
// Try Easy Ones in Order
// For hard Ones if one questions repeated WA
// then Choose Next Question
// some time question is not always what it seems, some time you dont
// just need whole process, its all about ans, example char count, some

int GCD(int a,int b)
{
if(b>a)
{
return GCD(b,a);
}
if(b==0)
{
return a;
}
return GCD(b,a%b);
}

int pow1(int a, int b)
{
int x = 1;
while(b)
{
if (b & 1)
{
x = (x * a) % mod;
}
a = (a * a) % mod;
b = b >> 1;
}
return x;
}
int pow2(int a, int b)
{
int one=1;
int x = one;
while(b)
{
if (b & one)
{
x = (x * a);
}
a = (a * a);
b = b >>one;
}
return x;
}
int max3(int a, int b, int c)
{
if (a >= b && a >= c)
{
return a;
}
if (b >= a && b >= c)
{
return b;
}
return c;
}
int min3(int a, int b, int c)
{
if (a <= b && a <= c)
{
return a;
}
if (b <= a && b <= c)
{
return b;
}
return c;
}
int nc2(int n)
{
int d=(n*(n-1))/2;
return d;
}
int maxar(int ar[], int n)
{
int k = ar[0];
for (int i = 1; i < n; i++)
{
if (k < ar[i])
{
k = ar[i];
}
}
return k;
}
int minar(int ar[],int n)
{
int k=ar[0];
for(int i=1;i<n;i++)
{
if(ar[i]<k)
{
k=ar[i];
}
}
return k;
}
void swap(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}
void yes()
{
cout << "Yes\n";
}
void no()
{
cout << "No\n";
}

int mulmod(int a, int b, int m)//It returns true if number is prime otherwise false
{
int x = 0,y = a % m;
while (b > 0) {
if (b % 2 == 1) {
x = (x + y) % m;
}
y = (y * 2) % m;
b /= 2;
}
return x % m;
}
int modulo(int base, int  e, int m) {
int x = 1;
int y = base;
while (e > 0) {
if (e % 2 == 1)
x = (x * y) % m;
y = (y * y) % m;
e = e / 2;
}
return x % m;
}

bool Miller(int p, int iteration) {
if (p < 2) {
return false;
}
if (p != 2 && p % 2==0) {
return false;
}
int s = p - 1;
while (s % 2 == 0) {
s /= 2;
}
for (int i = 0; i < iteration; i++) {
int a = rand() % (p - 1) + 1, temp = s;
int mod = modulo(a, temp, p);
while (temp != p - 1 && mod != 1 && mod != p - 1) {
mod = mulmod(mod, mod, p);
temp *= 2;
}
if (mod != p - 1 && temp % 2 == 0) {
return false;
}
}
return true;
}
int XOR(int n)
{

if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;

return 0;
}

void solve(int t1)
{
int n;
cin>>n;
string s;
cin>>s;

int z=0,o=0;
for(char i:s)
{
if(i=='0')
{
z++;
}
else
{
o++;
}
}
if(z==0||o==0)
{
cout<<s.length()<<" "<<"0\n";
return;
}
vector<pair<int,int> >ans;
while(s.length()>1)
{
unordered_map<int,int>mp;
mp[0]=0;
int sum=0;
int l=-1,r=-1;
for(int i=0;i<s.length();i++)
{
if(s[i]=='0')
{
sum--;
}
else
{
sum++;
}
if(mp.find(sum)==mp.end())
{
mp[sum]=i+1;
}
else
{
//cout<<mp[sum]<<" is \n";
if(i+2-mp[sum]>(r-l+1))
{
l=mp[sum];
r=i+1;
}
}
}
ans.push_back(make_pair(l,r));
string z1="";
for(int i=0;i<l;i++)
{
z1+=s[i];
}
if(z<=o)
{
z1+="0";
}
else
{
z1+="1";
}
for(int i=r;i<s.length();i++)
{
z1+=s[i];
}
//  cout<<r<<"\n";
s=z1;
//   cout<<z1<<"\n";
}
cout<<1<<" "<<ans.size()<<"\n";
for(pair<int,int>i:ans)
{
cout<<i.first+1<<" "<<i.second<<" ";
if(z<=o)
{
cout<<"0\n";
}
else
{
cout<<"1\n";
}
}

}

/* FOR STRINGS WHOLE LINE INPUT UISNG
string s;
getline(cin,s)+;
*/
/* IF AMOUNT OF DATA IS UNKNOWN THEN
while(cin>>x)
{
// CODE
}
*/
/* RANGE OF INT
-2 power 31 to 2 power 31 -1
RANGE OF LONG LONG
power 63
*/
// x=(x+m)%m;
// to compare double
/* if(abs(a-b)<1e-9)
{
equal
}
*/
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for(int i=1;i<=t;i++)
{
solve(i);
}
}

/*
1
7
248 496 781 86 859 868 821
*/``````

## Binary Substitution CodeChef Solution in Java

``````/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t>0){
int n = sc.nextInt();
String s = sc.next();
StringBuffer sb = new StringBuffer(s);

int count0 = 0;
int count1 = 0;
for(int i=0; i<n; i++){
if(s.charAt(i)=='0'){count0++;}
else{count1++;}
}

if(count0==n || count1==n){
System.out.println(n+" "+0);
}
else{
int c = 0;
if(count1<count0){c=1;}

int diff = Math.abs(count0-count1) + 1;

ArrayList<int[]> arr = new ArrayList<int[]>();

for(int i=1; i<diff; ++i){
int j = 1;
while(sb.charAt(j)==sb.charAt(j-1)){j++;}

int[] temp = {j, j+1, c};
sb.replace(j-1, j+1, String.valueOf(c));
}

int[] temp = {1, sb.length(), 0};

System.out.println(1+" "+arr.size());

for(int j=0; j<arr.size(); j++){
int[] temp1 = arr.get(j);
for(int k=0; k<temp1.length; k++){
System.out.print(temp1[k]+" ");
}
System.out.println(" ");
}
}

t--;
}
}
}
``````

## Binary Substitution CodeChef Solution in Pyth 3

``````# cook your dish here
def fm(nums):
h={}
count=0
ans=[0,-1]
for i in range(len(nums)):
current=nums[i]
if current=='0':
count-=1
else:
count+=1

if count==0:
ans=[0,i]
if count in h:
if (i-h[count])>(ans[1]-ans[0]+1):
ans=[h[count]+1,i]
else:
h[count]=i
return ans
t=int(input())
while(t):
t-=1
k=int(input())
s=str(input())
zero=s.count('0')
one=len(s)-zero
ff=[]
steps=0
while(zero and one):

temp=fm(s)
#print(temp,mm)
zero-=(temp[1]-temp[0]+1)//2
one-=(temp[1]-temp[0]+1)//2
x='0'
if zero>=one:
x='1'
s=s[:temp[0]]+x+ s[temp[1]+1:]
if int(x):
one+=1
else:
zero+=1
steps+=1
ff.append([temp[0]+1,temp[1]+1,int(x)])

print(max(zero,one,int(x)),steps)
for i in ff:
print(*i)
``````
##### Binary Substitution CodeChef Solution Review:

In our experience, we suggest you solve this Binary Substitution CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Binary Substitution CodeChef Solution

Find on CodeChef

##### Conclusion:

I hope this Binary Substitution CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions