Separate ‘1’ and ‘0’ in a binary string in C++
By Astha AwasthiIn this tutorial, we are going to discuss on a binary string problem, Separate ‘1’ and ‘0’ in a binary string in C++.
Separate ‘1’ and ‘0’ in a binary string in C++
These type of problem are being useful for an interview or in a coding round of top-IT companies and also being useful for competitive programming contests. These type of problems are being asked in various competitive programming contests in different ways. So, in this post, i am going to discuss the basic of that problem and solve it in the best way in O(n) time complexity.
What is a binary string?
Binary string is a string which consists of all elements value 0 and 1 only.
Ex:- 111000111001
Problem Statement
We are provided with a binary string of ‘0’ and ‘1’ only. We need to separate all 1’s on one side and 0 on another in binary string. We need to perform operation for this, In each operation we can only swap adjacent 1 and 0’s.
We need to find out the minimum number of operations to segregate all 1 and 0’s.
Example:-
String :- 1010101
OUTPUT:- 1111000
Approach:-
- Read the binary string.
- We have two options either we can shift all 0’s on right side and all 1’s on left side or vice-versa.
- So, we need to check number of operations for both and print the minimum of two operations.
- Whenever we got 1 we count it and check how many 0 are on its left side that number of swaps we needed to put 1 on left side and all zero on the right side.
- Similarly, we perform the same operation when we got 0 in binary string.
- Minimum of the above two operations will be our answer.
C++ code implementation of segregation of 1’s and 0’s in a binary string
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin>>s;
long long one=0,zero=0;
long long ans1=0,ans2=0;
for(int i=0;i<s.length();i++)
{
if(s[i]=='1')
{
one++;
ans1+=zero;
}
else
{
zero++;
ans2+=one;
}
}
cout<<min(ans1,ans2)<<endl;
}
INPUT
001010
OUTPUT
3
This was the solution of the problem: Separate ‘1’ and ‘0’ in a binary string in C++
I hope you got the basic of these kinds of problems. These problems can be asked in different ways also by changing characters 0 and 1 in a string.
You can ask your doubts in the comment section below. Keep reading and stay tuned.
Thank You !!
Also learn:
Leave a Reply