Given binary string str, the task is to find the minimum number of characters required to be flipped to make all 1s in right and 0s in left.
Examples:
Input: str = “100101”
Output: 2
Explanation:
Flipping str[0] and str[4] modifies str = “000111”. Therefore, the required output is 2.Input: S = “00101001”
Output: 2
Explanation:
Flipping str[2] and str[4] modifies str = “00000001”. Therefore, the required output is 2.
Approach: The idea is to count the number of 0s on the right side of each index of the string and count the number of 1s on the left side of each index of the string. Follow the steps below to solve the problem:
- Initialize a variable, say cntzero, to store the total count of 0s in the given string.
- Traverse the string and count the total number of 0s in the given string.
- If cntzero in the given string is 0, or equal to the length of the string, the result will be 0.
- Traverse the string and for each index, find the sum of the count of 1s on the left side of the index and the count of 0s on the right side of the index.
- Find the minimum value from all sums obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum count// of flips required to make all 1s on// the right and all 0s on the left of// the given stringint minimumCntOfFlipsRequired(string str){ // Stores length of str int n = str.length(); // Store count of 0s in the string int zeros = 0; // Traverse the string for (int i = 0; i < n; i++) { // If current character is 0 if (str[i] == '0') { // Update zeros zeros++; } } // If count of 0s in the string // is 0 or n if (zeros == 0 || zeros == n) { return 0; } // Store minimum count of flips // required to make all 0s on // the left and all 1s on the right int minFlips = INT_MAX; // Stores count of 1s on the left // of each index int currOnes = 0; // Stores count of flips required to make // string monotonically increasing int flips; // Traverse the string for (int i = 0; i < n; i++) { // If current character // is 1 if (str[i] == '1') { // Update currOnes currOnes++; } // Update flips flips = currOnes + (zeros - (i + 1 - currOnes)); // Update the minimum // count of flips minFlips = min(minFlips, flips); } return minFlips;}// Driver Codeint main(){ string str = "100101"; cout << minimumCntOfFlipsRequired(str); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG { // Function to find the minimum count of flips // required to make all 1s on the right and // all 0s on the left of the given string public static int minimumCntOfFlipsRequired( String str) { // Stores length of str int n = str.length(); // Store count of 0s in the string int zeros = 0; // Traverse the string for (int i = 0; i < n; i++) { // If current character is 0 if (str.charAt(i) == '0') { // Update zeros zeros++; } } // If count of 0s in the string // is 0 or n if (zeros == 0 || zeros == n) { return 0; } // Store minimum count of flips // required to make all 0s on // the left and 1s on the right int minFlips = Integer.MAX_VALUE; // Stores count of 1s on the left // side of each index int currOnes = 0; // Stores count of flips required to make // all 0s on the left and 1s on the right int flips; // Traverse the string for (int i = 0; i < n; i++) { // If current character is 1 if (str.charAt(i) == '1') { // Update currOnes currOnes++; } // Update flips flips = currOnes + (zeros - (i + 1 - currOnes)); // Update the minimum // count of flips minFlips = Math.min(minFlips, flips); } return minFlips; } // Driver code public static void main(String[] args) { String s1 = "100101"; System.out.println(minimumCntOfFlipsRequired(s1)); }} |
Python3
# Python3 program to implement # the above approach# Function to find the minimum count# of flips required to make all 1s on# the right and all 0s on the left of# the given stringdef minimumCntOfFlipsRequired(str): # Stores length of str n = len(str); # Store count of 0s in the string zeros = 0; # Traverse the string for i in range(n): # If current character # is 0 if (str[i] == '0'): # Update zeros zeros += 1; # If count of 0s in the string # is 0 or n if (zeros == 0 or zeros == n): return 0; # Store minimum count of flips # required to make all 0s on the # left and all 1s on the right minFlips = 10000001; # Stores count of 1s on the left # of each index currOnes = 0; # Stores count of flips required to make # all 0s on the left and all 1s on the right flips = 0; # Traverse the string for i in range(n): # If current character is 1 if (str[i] == '1'): # Update currOnes currOnes += 1; # Update flips flips = currOnes + (zeros - (i + 1 - currOnes)); # Update the minimum # count of flips minFlips = min(minFlips, flips); return minFlips;# Driver Codeif __name__ == '__main__': str = "100101"; print(minimumCntOfFlipsRequired(str)); |
C#
// C# program to implement// the above approach using System; class GFG{ // Function to find the minimum count of flips// required to make all 1s on the right and// all 0s on the left of the given stringpublic static int minimumCntOfFlipsRequired(string str){ // Stores length of str int n = str.Length; // Store count of 0s in the string int zeros = 0; // Traverse the string for(int i = 0; i < n; i++) { // If current character is 0 if (str[i] == '0') { // Update zeros zeros++; } } // If count of 0s in the string // is 0 or n if (zeros == 0 || zeros == n) { return 0; } // Store minimum count of flips // required to make all 0s on // the left and 1s on the right int minFlips = Int32.MaxValue; // Stores count of 1s on the left // side of each index int currOnes = 0; // Stores count of flips required // to make all 0s on the left and // 1s on the right int flips; // Traverse the string for(int i = 0; i < n; i++) { // If current character is 1 if (str[i] == '1') { // Update currOnes currOnes++; } // Update flips flips = currOnes + (zeros - (i + 1 - currOnes)); // Update the minimum // count of flips minFlips = Math.Min(minFlips, flips); } return minFlips;}// Driver codepublic static void Main(){ string s1 = "100101"; Console.WriteLine(minimumCntOfFlipsRequired(s1));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program to implement// the above approach // Function to find the minimum count of flips // required to make all 1s on the right and // all 0s on the left of the given string function minimumCntOfFlipsRequired(str) { // Stores length of str let n = str.length; // Store count of 0s in the string let zeros = 0; // Traverse the string for (let i = 0; i < n; i++) { // If current character is 0 if (str[i] == '0') { // Update zeros zeros++; } } // If count of 0s in the string // is 0 or n if (zeros == 0 || zeros == n) { return 0; } // Store minimum count of flips // required to make all 0s on // the left and 1s on the right let minFlips = Number.MAX_VALUE; // Stores count of 1s on the left // side of each index let currOnes = 0; // Stores count of flips required to make // all 0s on the left and 1s on the right let flips; // Traverse the string for (let i = 0; i < n; i++) { // If current character is 1 if (str[i] == '1') { // Update currOnes currOnes++; } // Update flips flips = currOnes + (zeros - (i + 1 - currOnes)); // Update the minimum // count of flips minFlips = Math.min(minFlips, flips); } return minFlips; } // Driver Code let s1 = "100101"; document.write(minimumCntOfFlipsRequired(s1));</script> |
Output
2
Time Complexity: O(N), where N is the length of the string
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
