Minimize flips required such that string does not any pair of consecutive 0s
Given a binary string S, the task is to find the minimum count of flips required to modify a string such that it does not contain any pair of consecutive 0s.
Examples:
Input: S = “10001”
Output: 1
Explanation:
Flipping S[2] modifies S to “10101”.
Therefore, the required output is 1.Input: S = “100001”
Output: 2
Explanation:
Flipping S[1] modifies S to “110001”.
Flipping S[3] modifies S to “110101”.
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Iterate over the characters of the string. For every ith character, check if S[i] and S[i + 1] are equal to ‘0’ or not. If found to be true, then increment count and update S[i + 1] to ‘1’.
- Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum flips required // such that a string does not contain // any pair of consecutive 0s bool cntMinOperation(string S, int N) { // Stores minimum count of flips int cntOp = 0; // Iterate over the characters // of the string for ( int i = 0; i < N - 1; i++) { // If two consecutive characters // are equal to '0' if (S[i] == '0' && S[i + 1] == '0' ) { // Update S[i + 1] S[i + 1] = '1' ; // Update cntOp cntOp += 1; } } return cntOp; } // Driver Code int main() { string S = "10001" ; int N = S.length(); cout << cntMinOperation(S, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find minimum flips required // such that a String does not contain // any pair of consecutive 0s static int cntMinOperation( char []S, int N) { // Stores minimum count of flips int cntOp = 0 ; // Iterate over the characters // of the String for ( int i = 0 ; i < N - 1 ; i++) { // If two consecutive characters // are equal to '0' if (S[i] == '0' && S[i + 1 ] == '0' ) { // Update S[i + 1] S[i + 1 ] = '1' ; // Update cntOp cntOp += 1 ; } } return cntOp; } // Driver Code public static void main(String[] args) { String S = "10001" ; int N = S.length(); System.out.print(cntMinOperation(S.toCharArray(), N)); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function to find minimum flips required # such that a string does not contain # any pair of consecutive 0s def cntMinOperation(S, N): # Stores minimum count of flips cntOp = 0 # Iterate over the characters # of the string for i in range (N - 1 ): # If two consecutive characters # are equal to '0' if (S[i] = = '0' and S[i + 1 ] = = '0' ): # Update S[i + 1] S[i + 1 ] = '1' # Update cntOp cntOp + = 1 return cntOp # Driver Code if __name__ = = '__main__' : S = "10001" N = len (S) print (cntMinOperation([i for i in S], N)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG { // Function to find minimum flips required // such that a String does not contain // any pair of consecutive 0s static int cntMinOperation( char []S, int N) { // Stores minimum count of flips int cntOp = 0; // Iterate over the characters // of the String for ( int i = 0; i < N - 1; i++) { // If two consecutive characters // are equal to '0' if (S[i] == '0' && S[i + 1] == '0' ) { // Update S[i + 1] S[i + 1] = '1' ; // Update cntOp cntOp += 1; } } return cntOp; } // Driver Code public static void Main( string [] args) { string S = "10001" ; int N = S.Length; Console.WriteLine(cntMinOperation(S.ToCharArray(), N)); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript program for the above approach // Function to find minimum flips required // such that a String does not contain // any pair of consecutive 0s function cntMinOperation(S, N) { // Stores minimum count of flips let cntOp = 0; // Iterate over the characters // of the String for (let i = 0; i < N - 1; i++) { // If two consecutive characters // are equal to '0' if (S[i] == '0' && S[i + 1] == '0' ) { // Update S[i + 1] S[i + 1] = '1' ; // Update cntOp cntOp += 1; } } return cntOp; } let S = "10001" ; let N = S.length; document.write(cntMinOperation(S.split( '' ), N)); </script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us