Given a binary string S of even size that contains only 0s and 1s, the task is to find the minimum flips (that is 0 to 1 or 1 to 0) such that every contiguous subsegment that contains the same bit is of even size.
Examples:
Input: S = “1110011000 “
Output: 3
Explanation: Change S[2], S[5] and S[6] to ‘0’.
After that S becomes “1100000000”, it can be divided into
“11” and “00000000”, which have lengths 2 and 8 respectively.
There are other ways to operate 3 times such as
“1111110000”, “1100001100”, “1111001100”.Input: 100110
Output: 3
Explanation: The given string can be converted into 000000
with 3 operations or 111111.
Approach: To solve the problem follow the below observations:
It can be said that we have to divide the string into many adjacent binaries with the length of 2 where the strings will be either 00 or 11. So, we have to only take care of sequence where s[i] != s[i+1]
- Now in order to find a minimum operation sequence like “1011” should be converted to “1111” and “0100” should be converted to “0000”.
- So, the minimum number of operations is 1. Hence once we make s[i] = s[i + 1] we will move i to i+2 to check whether they are equal or not.
Follow the steps mentioned below to implement the idea:
- Iterate from i = 0 to N-1:
- Check if S[i] is the same as S[i+1].
- If they are the same then no bit flip is required.
- Otherwise, increment the number of flips by 1.
- After each check move from i to i+2.
- The total number of flips calculated is the required minimum answer.
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number of bit flipsint solve(string s){ // Variable to store the minimum number of flips int ans = 0; int n = s.size(); // Increment i by 2 for (int i = 0; i < n; i += 2) { if (s[i] != s[i + 1]) ans++; } // Return the answer return ans;}// Driver codeint main(){ string S = "1110011000"; // Function Call cout << solve(S); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum number of bit flips static int solve(String s) { // Variable to store the minimum number of flips int ans = 0; int n = s.length(); // Increment i by 2 for (int i = 0; i < n; i += 2) { if (s.charAt(i) != s.charAt(i+1)) ans++; } // Return the answer return ans; } // Driver Code public static void main(String[] args) { String S = "1110011000"; // Function Call System.out.print(solve(S)); }}// This code is contributed by sanjoy_62. |
Python3
# Python code to implement the above approach# Function to find the minimum number of bit flipsdef solve(s): # Variable to store the minimum number of flips ans = 0 n = len(s) # Increment i by 2 for i in range(0, n, +2): if(s[i] is not s[i+1]): ans += 1 # Return the answer return ansS = "1110011000"# Function callprint(solve(S))# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG{ // Function to find the minimum number of bit flips static int solve(string s) { // Variable to store the minimum number of flips int ans = 0; int n = s.Length; // Increment i by 2 for (int i = 0; i < n; i += 2) { if (s[i] != s[i+1]) ans++; } // Return the answer return ans; } // Driver Code public static void Main() { string S = "1110011000"; // Function Call Console.WriteLine(solve(S)); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code for the above approach // Function to find the minimum number of bit flips function solve(s) { // Variable to store the minimum number of flips let ans = 0; let n = s.length; // Increment i by 2 for (let i = 0; i < n; i += 2) { if (s[i] != s[i + 1]) ans++; } // Return the answer return ans; } // Driver code let S = "1110011000"; // Function Call document.write(solve(S)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- We start by defining a function solve that takes a string s as input and returns an integer.
- We then initialize the variables n, count, and flips. n is the length of the string s, count is the length of the current segment, and flips is the number of flips needed.
- We then loop through the string s starting from the second character (i=1) to the end (i<n).
- Inside the loop, we check if the current character s[i] is different from the previous character s[i-1]. If it is different, we have a new segment and we increment the count variable.
- If the current character s[i] is the same as the previous character s[i-1], we check if the length of the current segment count is odd. If it is odd, we need to flip one bit in that segment to make it even, so we increment the flips variable.
- We then reset the count variable to 1 for the next segment.
- After the loop, we need to check the length of the last segment, which may not have been accounted for in the loop. If it is odd, we need to flip one bit in that segment to make it even, so we increment the flips variable again.
- Finally, we return the total number of flips needed.
Below is the implementation of the above approach:
C++
#include <iostream>using namespace std;int solve(string s) { int n = s.size(); int count = 0, flips = 0; for (int i = 1; i < n; i++) { if (s[i] != s[i-1]) { count++; } else { if (count % 2 == 1) { flips++; } count = 1; } } if (count % 2 == 1) { flips++; } return flips;}int main(){ string S = "1110011000"; // Function Call cout << solve(S); return 0;} |
Java
import java.util.*;public class Main { public static int solve(String s) { int n = s.length(); int count = 0, flips = 0; for (int i = 1; i < n; i++) { if (s.charAt(i) != s.charAt(i-1)) { count++; } else { if (count % 2 == 1) { flips++; } count = 1; } } if (count % 2 == 1) { flips++; } return flips; } public static void main(String[] args) { String S = "1110011000"; // Function Call System.out.println(solve(S)); }} |
Python3
def solve(s): # Get the length of the string n = len(s) # Initialize variables count = 0 flips = 0 # Loop through the string for i in range(1, n): # If the current character is different from the previous one if s[i] != s[i-1]: count += 1 else: # If the count is odd, increment flips if count % 2 == 1: flips += 1 count = 1 # If the count is odd, increment flips if count % 2 == 1: flips += 1 # Return the number of flips return flips# Define the input stringS = "1110011000"# Function Callprint(solve(S)) |
C#
using System;namespace CodeTranslation{ class Program { static int Solve(string s) { // Get the length of the string int n = s.Length; // Initialize variables int count = 0, flips = 0; // Loop through the string for (int i = 1; i < n; i++) { // If the current character is different from the previous one if (s[i] != s[i - 1]) { count++; } else { // If the count is odd, increment flips if (count % 2 == 1) { flips++; } count = 1; } } // If the count is odd, increment flips if (count % 2 == 1) { flips++; } // Return the number of flips return flips; } static void Main(string[] args) { string S = "1110011000"; // Function Call Console.WriteLine(Solve(S)); } }} |
Javascript
function solve(s) { let n = s.length; let count = 0, flips = 0; // Iterate through the string for (let i = 1; i < n; i++) { // If the current character is different from the previous one if (s[i] != s[i - 1]) { count++; } else { // If the count of different characters is odd if (count % 2 == 1) { flips++; } count = 1; } } // Check for the last segment of different characters if (count % 2 == 1) { flips++; } return flips;}// Define the input stringlet S = "1110011000";// function callconsole.log(solve(S)); |
Output
3
Time complexity: O(N)
Auxiliary Space: O(1)
