Header Ads Widget

Sort String | hackerearth solution

Rajnish Tripathi 21:09

 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

1≤�≤1051≤�≤3⋅105���������′0′����′1′�.�����������������������������������3⋅105.

 

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

Tags:

Post a Comment

0 Comments