# Sort String | hackerearth solution

Problem

You are given a binary string $�$ of length $�$. You can apply the following operation to the string $�$ :

• Choose two distinct indices $�,�\phantom{\rule{thickmathspace}{0ex}}\left(1\le �,�\le �,�\ne �\right)$ and flip the characters ${�}_{�},{�}_{�}$.

Find the minimum number of operations required to sort the given string $�$. It is always possible to sort any string under the given constraints.

Input format

• The first line contains $�$ denoting the number of test cases. The description of $�$ test cases is as follows:
• For each test case:
• The first line contains $�$ denoting the length of string $�$.
• The second line contains the binary string $�$.

Output format

For each test case, print the minimum number of operations required to sort the given string $�$.

Constraints

$1\le �\le {10}^{5}\phantom{\rule{0ex}{0ex}}1\le �\le 3\cdot {10}^{5}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}�\phantom{\rule{thickmathspace}{0ex}}��������{\phantom{\rule{thickmathspace}{0ex}}}^{\prime }{0}^{\prime }�\phantom{\rule{thickmathspace}{0ex}}���{\phantom{\rule{thickmathspace}{0ex}}}^{\prime }{1}^{\prime }�.\phantom{\rule{0ex}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}��\phantom{\rule{thickmathspace}{0ex}}�\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}�����\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}������\phantom{\rule{thickmathspace}{0ex}}3\cdot {10}^{5}.$

Sample Input
2
3
101
6
110100

Sample Output
1
2

Time Limit: 10
Memory Limit: 256
Source Limit:
Explanation

In the first test case, choose $�=1,�=3$ and flip ${�}_{1},{�}_{3}$ making $�=111$ which is a sorted string.

In the second test case, choose $�=1,�=2$ and flip ${�}_{1},{�}_{3}$ making $�=000100$, then  choose $�=5,�=6$ and flip ${�}_{5},{�}_{6}$ making $�=000111$, which is a sorted string.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n; cin>>n;
string s; cin>>s;
int zerr = 0, ones = 0;
for(auto &x : s){
zerr += (x == '0');
ones += (x == '1');
}
int ans = 0;
if(!zerr or !ones){
cout<<ans<<endl;
return;
}
ans = 1e9;
if(zerr%2 == 0){
ans = zerr/2;
}
if(ones%2 == 0){
ans = min(ans,ones/2);
}
ones = 0;
for(auto &x : s){
if(x=='0'){
zerr--;
}
else{
ones++;
}
if((zerr + ones)%2 == 0){
ans = min(ans,(zerr+ones)/2);
}
}
cout<<ans<<endl;
}
int32_t main()
{
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE //file start
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif //file end
// int cases=1;
int t; cin>>t;
while(t--)
solve();
return 0;
}

Code(JAVA 8):-

import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int N = sc.nextInt();
String S = sc.next();
int countOnes = 0;
int countFlips = 0;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == '0') {
// Don't flip it
int x = countOnes;
// Flip
int y = countFlips + 1;
countFlips = Math.min (x, y);
} else {
++countOnes;
}
}
countFlips = (countFlips + 1) / 2;
System.out.println(countFlips);
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-