Number of flips to make binary string alternate in C++

January 4, 2022

Number of flips to make binary string alternate

Today in this article we will be discussing how to find the Number of flips to make binary string alternate.

Lets understand this with the help of example :- 

  • Input:- 001

  • Output:- 1

here we jusst need to flip 1st bit from 0 to 1 and that will make the binary string as “101” and this is binary alternate string.  

flips to make binary string alternate

Algorithm

  • We can convert the original string to alternate binary string in 2 ways 

          Case 1 :- 0 1 0 1 0 1 0 1 0 1

          Case 2 :- 1 0 1 0 1 0 1 0 1 0

  • Initialize two variables count1 and count2 that will count the number of flips required to make the binary string alternate.
  • We will iterate throughout the string and will count the number of flips required to convert.
  • Then print the minimum of both the count1 and count2.
Check If String Is Shuffled Substring of Another String

C++ Code :-

#include<bits/stdc++.h>

using namespace std;

int main()

{
        string s = "001";
        int c1=0,c2=0;

        for(int i=0;i<s.length();i++){
            if(i&1 and s[i] == '0') c1++;
            if(i%2==0 and s[i]=='1') c1++;
            if(i&1 and s[i] == '1') c2++;
            if(i%2==0 and s[i]=='0') c2++;
        }
        cout<<"Minimum number of flips required = "<<min(c1,c2);

    return 0;
}

Output:-

Minimum number of flips required = 1