Separate 1's and 0's in a binary string into separate halves

In this tutorial, we need to split all the 1s and 0s of the given binary string into two halves. Here, we need to take a substring from the given string and reverse it to separate different parts of 0 and 1. Ultimately, we need to calculate the total number of inversions required for the substring to split the 1 and 0 in half.

Problem Statement - We are given a binary string of even length. We need to take any substring from the given string multiple times and reverse it to split it into two halves. We need to print the total number of required reversals at the end.

Example

Input –  str = 0011

Output – 0

illustrate

We need 0 reversals because the string is split in half.

Input –  str = 0011101000

Output – 2

illustrate

• First, take the substring of length 2 starting from the 5th index and reverse it. The resulting string will be 0011110000.

• After that, take a string of length 6 from the beginning and reverse it. The resulting string will be 1111000000

Input –  str = 010101

Output – 2

illustrate

• Reverse a string of length 2 starting from the first index. The resulting string will be 001101.

• Now, reverse the string of length 3 starting at the second index. The final string will be 000111.

method 1

This method will count the total number of distinct adjacent elements. After that, we can say that the total number of reversals required is count / 2.

Let's understand it by debugging the sample input.

Input –  str = 00111010

So, the total number of different adjacent elements is 4. Here, str[1] != str[2], str[4] != str[5], str[5] != str[6], and str[6] != str[7].

So, the count value is 4, and the answer is count/2, which is equal to 2.

algorithm

• Step 1 - Initialize the "cnt" variable to 0.

• Step 2 - Use a for loop and iterate over the string.

• Step 3 − In the for loop, if the current element is not equal to the previous element, increase the value of the ‘cnt’ variable by 1.

• Step 4 − If the value of 'cnt' is an odd number, return (cnt -1) /2. Otherwise, return cnt/2.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
//  function to find the minimum number of reversals required to segregate 1s and 0s in a separate half
int minimumReversal(string str, int len){
   int cnt = 0; // initialize count with zero
   for (int i = 1; i < len; i++){
   
      // if the adjacent elements are not the same, then the increment count
      if (str[i] != str[i - 1]){
         cnt++;
      }
   }
   
   // For odd count
   if (cnt % 2 == 1){
      return (cnt - 1) / 2;
   }
   return cnt / 2; // For even count
}
int main(){
   string str = "00111010";
   int len = str.size();
   cout << "Minimum number of operations required is : " << minimumReversal(str, len);
   return 0;
}

Output

Minimum number of operations required is : 2

Time complexity - O(N), since we iterate over the string.

Space complexity - O(N), since we use constant space to store the count.

Here, we use the logic that needs to be reversed whenever two different adjacent elements are found. Furthermore, in a single reverse operation we can set two elements, so we return count/2 as the result value.

The above is the detailed content of Separate 1's and 0's in a binary string into separate halves. For more information, please follow other related articles on the PHP Chinese website!