Home > Article > Backend Development > 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.
Input – str = 0011
Output – 0
We need 0 reversals because the string is split in half.
Input – str = 0011101000
Output – 2
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
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.
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.
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.
#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; }
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!