Header Ads Widget

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 ,(1,,) 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

11051310501.3105.

 

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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-