Problem
You are given a binary string of length . You can apply the following operation to the string :
- Choose two distinct indices 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
Time Limit: 10
Memory Limit: 256
Source Limit:
Explanation
In the first test case, choose and flip making which is a sorted string.
In the second test case, choose and flip making , then choose and flip making , 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:-
- Swap the adjacent characters of the string
- Double the vowel characters in the string
- Character with their frequency
- Program to find the closest value
Must check this:-
Companies interview:-
- Swap adjacent characters
- Double the vowel characters
- Check valid parenthesis
- Print the characters with their frequencies
- Find closest value
- Word Count
- Program of CaesarCipher
- Program to find the perfect city
- Annual Day | Tech Mahindra coding question
- Find the number of pairs in the array whose sum is equal to a given target.
Full C course:-
Key points:-
- How to set limit in the floating value in python
- What is boolean data type
- How to print any character without using format specifier
- How to check that given number is power of 2 or not
- How to fix limit in double and floating numbers after dot (.) in c++
- How to print a double or floating point number in scientific notation and fixed notation
- How to take input a string in c
- How to reduce the execution time of program in c++.
Cracking the coding interview:-
Array and string:-
Tree and graph:-
Hackerearth Problems:-
- Very Cool numbers | Hacker earth solution
- Vowel Recognition | Hackerearth practice problem solution
- Birthday party | Hacker earth solution
- Most frequent | hacker earth problem solution
- program to find symetric difference of two sets
- cost of balloons | Hacker earth problem solution
- Chacha o chacha | hacker earth problem solution
- jadu and dna | hacker earth solution
- Bricks game | hacker earth problem
- Anti-Palindrome strings | hacker earth solution
- connected components in the graph | hacker earth data structure
- odd one out || hacker earth problem solution
- Minimum addition | Hackerearth Practice problem
- The magical mountain | Hackerearth Practice problem
- The first overtake | Hackerearth Practice problem
Hackerrank Problems:-
- Playing With Characters | Hackerrank practice problem solution
- Sum and Difference of Two Numbers | hackerrank practice problem solution
- Functions in C | hackerrank practice problem solution
- Pointers in C | hackerrank practice problem solution
- Conditional Statements in C | Hackerrank practice problem solution
- For Loop in C | hackerrank practice problem solution
- Sum of Digits of a Five Digit Number | hackerrank practice problem solution
- 1D Arrays in C | hackerrank practice problem solution
- Array Reversal | hackerrank practice problem solution
- Printing Tokens | hackerrank practice problem solution
- Digit Frequency | hackerrank practice problem solution
- Calculate the Nth term | hackerrank practice problem solution
Data structure:-
- Program to find cycle in the graph
- Implementation of singly link list
- Implementation of queue by using link list
- Algorithm of quick sort
- stack by using link list
- program to find preorder post order and inorder of the binary search tree
- Minimum weight of spanning tree
- Preorder, inorder and post order traversal of the tree
MCQs:-
0 Comments