Minimum number of moves required to place all 0's before 1's in a binary string

Problem Statement

We are given a binary string str and we are asked to remove the minimum number of characters from the string so that we can put all zeros before 1's.

Example

enter

str = ‘00110100111’

Output

3

illustrate

Here, we can achieve output 3 in two ways.

We can remove arr[2], arr[3] and arr[5] or arr[4], arr[6] and arr[7] from the string.

enter

str = ‘001101011’

Output

2

illustrate

We can remove arr[4] and arr[6] and put all zeros before ones.

enter

str = ‘000111’

Output

0

illustrate

In the given string, all zeros have been placed before 1, so we don't need to remove any characters from the given string.

method 1

In the first method, we will use two arrays. The first array stores all 1's on the left and the other array stores all 0's on the right. After that, we can add the elements at i-th index in both arrays and find the minimum sum.

algorithm

• Step 1 - Define a named list of "zeros" and "ones" of length n, where n is the length of the string that we can get using the size() method.

• Step 2 - If the first character in the given string is "1", store 1 at the 0th index of the "ones" array; otherwise, store 0.

• Step 3 - Use a for loop to start traversing from the second element of the string. In the for loop, Ones[i] is initialized with the value obtained by adding Ones[i-1] to 1 or 0 based on the character of the string at index i.

• Step 4 - Store either 1 or 0 at Zeros[n-1] depending on the last character in the given string.

• Step 5 - Use a for loop to traverse the string starting from the second last character and update the value of the zero list based on the string characters.

• Step 6 - Define the "min_zeros_to_remove" variable and initialize it with the maximum integer value.

• Step 7 - Now, loop through the "zero" and "one" lists. Access values ​​from the "i 1" index in the zero list and the "I" index in the "one" list. After that, add these two elements.

• Step 8 - If the value of "min_zeros_to_remove" is less than the current value of the "min_zeros_to_remove" variable, change its value to the sum of the two array elements.

• Step 9 - Return the result value.

Example

#include <bits/stdc++.h>
using namespace std;

int minimumZeroRemoval(string str){
   int n = str.size();
   // arrays to store the prefix sums of zeros and ones
   vector<int> zeros(n);
   vector<int> ones(n);
   // compute total number of 1s at the left of each index
   ones[0] = (str[0] == '1') ? 1 : 0;
   for (int i = 1; i < n; i++) {
      ones[i] = ones[i - 1] + ((str[i] == '1') ? 1 : 0);
   }
   // compute total number of 0s at the right of each index
   zeros[n - 1] = (str[n - 1] == '0') ? 1 : 0;
   for (int i = n - 2; i >= 0; i--){
      zeros[i] = zeros[i + 1] + ((str[i] == '0') ? 1 : 0);
   }
   // do the sum of zeros and ones for each index and return the minimum value
   int min_zeros_to_remove = INT_MAX;
   for (int i = 0; i < n - 1; i++){
      min_zeros_to_remove = min(min_zeros_to_remove, zeros[i + 1] + ones[i]);
   }
   return min_zeros_to_remove;
}
int main() {
   string str = "00110100111";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Output

The minimum number of zeros required to remove from the given string is - 3

• Time complexity - O(N) because we need a for loop to iterate over strings and lists of size N.

• Space Complexity - O(N) because we use two lists to store the counts of 1 and 0.

Method 2

This method is an optimized version of the first method. Here, instead of a list, we use two variables to store the count of 1s and 0s.

algorithm

• Step 1 - Define the "zeros_right" variable and initialize it with 0.

• Step 2 - Loop through the string, count the total number of "0" characters in the given string, and update the value of the "zero_right" variable accordingly.

• Step 3 - Define the "ones_left" variable and initialize it to 0.

• Step 4 - Use a for loop to iterate through the string. If the character at index i in the string is "1", increase the value of the "ones_left" variable by 1. Otherwise, reduce the value of the "zeros_right" variable by 1.

• Step 5 - If "zeros_right Ones_left" is less than the current value of the "res" variable, update the value of the "res" variable.

Example

#include <bits/stdc++.h>
using namespace std;

// function to remove zeros from the string to place all zeros before 1.
int minimumZeroRemoval(string str){
   // counting the total number of zeros in the given string
   int zeros_right = 0;
   for (int i = 0; i < str.size(); i++) {
      if (str[i] == '0')
      zeros_right += 1;
   }
   // variable to store the number of ones from left
   int ones_left = 0;
   // Size of the string
   int len = str.size();
   // variable to store the final result
   int result = INT_MAX;
   // Traverse the string from left to right
   for (int i = 0; i < len; i++){
      // If the current character is '1', then increment ones_left by 1 else, decrement zeros_right by 1
      if (str[i] == '1') {
         ones_left += 1;
      } else {
         zeros_right -= 1;
      }
      // Store the minimum result and zeros_right + ones_left in result
      result = min(result, zeros_right + ones_left);
   }
   // Return the final result
   return result;
}
int main() {
   string str = "001101011";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Output

The minimum number of zeros required to remove from the given string is - 2

• Time Complexity - O(N), when we iterate over the string.

• Space Complexity - O(1) since we only use constant space.

in conclusion

The user learned two ways to remove the minimum number of characters from a given binary string. The code for the second approach is more readable because we use variables to store the count of zeros and ones instead of using a list.

The above is the detailed content of Minimum number of moves required to place all 0's before 1's in a binary string. For more information, please follow other related articles on the PHP Chinese website!