Separate ‘1’ and ‘0’ in a binary string in C++

By Astha Awasthi

In 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