Given two binary strings A and B of length N, the task is to convert the string from A to string B by repeatedly flipping all the bits of a prefix of A, i.e. convert all the 0s in the prefix to 1s and vice-versa and print the minimum number of prefix flips required and the length of respective prefixes.
Examples:
Input: A = “001”, B = “000”
Output:
2
3 2
Explanation:
Flipping the prefix “001” modifies the string to “110”.
Flipping the prefix “11” modifies the string to “000”.Input: A = “1000”, B = “1011”
Output:
2
4 2
Explanation:
Flipping the prefix “1000” modifies the string to “0111”.
Flipping the prefix “01” modifies the string to “1011”.
Naive Approach: The simplest approach is to traverse the string A in reverse and for every ith character obtained such that A[i] is not equal to B[i], flip the characters present in A from indices [0, i] and increment the number of operations by 1. After complete traversal of the string, print the count of operations and the prefix length chosen in each operation.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The idea is to fix one bit at a time by traversing the string A in reverse. Maintain a boolean variable, say invert, initially set to false, to denote whether the current bits in A are flipped or not. While traversing, perform the following:
- If the iᵗʰ bit in A is not equal to the iᵗʰ bit in B and invert is false, then increment the count of operations and set invert to true.
- Otherwise, if the iᵗʰ bit in A is equal to the iᵗʰ bit in B and invert is true, then increment the count of operations and set invert to false.
Follow the steps below to solve the problem:
- Initialize a boolean variable, say invert as false, to denote whether the bits in A are flipped or not.
- Initialize an empty array, say res, to store the prefix length in each operation.
- Iterate in the range [N – 1, 0] using the variable i and perform the following steps:
- If A[i] != B[i] and invert is false, then the current bit is required to be flipped. Therefore. insert (i + 1) into the array res and update invert to true.
- Otherwise, check if A[i] == B[i] and invert is true, then insert (i + 1) to res, and update invert to false.
- Print the size of the array res as the number of operations required to make the two strings equal.
- Then, print the values stored in res to denote the prefix length in each operation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count flips required// to make strings A and B equalvoid findOperations(string A, string B, int N){ // Stores the count of the // number of operations int operations = 0; // Stores the length of // the chosen prefixes vector<int> ops; // Stores if operations are // performed even or odd times bool invert = false; // Traverse the given string for (int i = N - 1; i >= 0; i--) { // If current characters in // the two strings are unequal if (A[i] != B[i]) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.push_back(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.push_back(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required cout << operations << endl; // Print the chosen prefix // length in each operation if (operations != 0) { for (auto x : ops) cout << x << " "; }}// Driver Codeint main(){ // Given binary strings string A = "001", B = "000"; int N = A.size(); findOperations(A, B, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count flips required// to make Strings A and B equalstatic void findOperations(String A, String B, int N){ // Stores the count of the // number of operations int operations = 0; // Stores the length of // the chosen prefixes Vector<Integer> ops = new Vector<>(); // Stores if operations are // performed even or odd times boolean invert = false; // Traverse the given String for (int i = N - 1; i >= 0; i--) { // If current characters in // the two Strings are unequal if (A.charAt(i) != B.charAt(i)) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.add(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.add(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required System.out.print(operations +"\n"); // Print the chosen prefix // length in each operation if (operations != 0) { for (int x : ops) System.out.print(x+ " "); }}// Driver Codepublic static void main(String[] args){ // Given binary Strings String A = "001", B = "000"; int N = A.length(); findOperations(A, B, N);}}// This code is contributed by Amit Katiyar |
Python3
# Python program for the above approach# Function to count flips required# to make strings A and B equaldef findOperations(A, B, N): # Stores the count of the # number of operations operations = 0 # Stores the length of # the chosen prefixes ops = [] # Stores if operations are # performed even or odd times invert = False # Traverse the given string for i in range(N - 1, -1, -1): # If current characters in # the two strings are unequal if (A[i] != B[i]): # If A[i] is not flipped if (not invert): # Increment count # of operations operations += 1 # Insert the length of # the chosen prefix ops.append(i + 1) # Update invert to true invert = True else: # If A[i] is flipped if (invert): # Increment count # of operations operations += 1 # Insert length of # the chosen prefix ops.append(i + 1) # Update invert to false invert = False # Print the number of # operations required print (operations) # Print the chosen prefix # length in each operation if (operations != 0): for x in ops: print(x, end = " ")# Driver Codeif __name__ == '__main__': # Given binary strings A, B = "001", "000" N = len(A) findOperations(A, B, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count flips required// to make Strings A and B equalstatic void findOperations(String A, String B, int N){ // Stores the count of the // number of operations int operations = 0; // Stores the length of // the chosen prefixes List<int> ops = new List<int>(); // Stores if operations are // performed even or odd times bool invert = false; // Traverse the given String for(int i = N - 1; i >= 0; i--) { // If current characters in // the two Strings are unequal if (A[i] != B[i]) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.Add(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.Add(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required Console.Write(operations + "\n"); // Print the chosen prefix // length in each operation if (operations != 0) { foreach(int x in ops) Console.Write(x + " "); }}// Driver Codepublic static void Main(String[] args){ // Given binary Strings String A = "001", B = "000"; int N = A.Length; findOperations(A, B, N);}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to count flips required // to make Strings A and B equal function findOperations(A, B, N) { // Stores the count of the // number of operations var operations = 0; // Stores the length of // the chosen prefixes var ops = []; // Stores if operations are // performed even or odd times var invert = false; // Traverse the given String for (var i = N - 1; i >= 0; i--) { // If current characters in // the two Strings are unequal if (A[i] !== B[i]) { // If A[i] is not flipped if (!invert) { // Increment count // of operations operations++; // Insert the length of // the chosen prefix ops.push(i + 1); // Update invert to true invert = true; } } else { // If A[i] is flipped if (invert) { // Increment count // of operations operations++; // Insert length of // the chosen prefix ops.push(i + 1); // Update invert to false invert = false; } } } // Print the number of // operations required document.write(operations + "<br>"); // Print the chosen prefix // length in each operation if (operations !== 0) { for (const x of ops) { document.write(x + " "); } } } // Driver Code // Given binary Strings var A = "001", B = "000"; var N = A.length; findOperations(A, B, N); </script> |
Output:
2 3 2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
