Convert a Binary String to another by flipping prefixes minimum number of times
Given two binary strings A and B of length N, the task is to convert the string A to B by repeatedly flipping a prefix of A, i.e. reverse the order of occurrence of bits in the chosen prefix. Print the number of flips required and the length of all prefixes.
Examples:
Input: A = β01β, B = β10β
Output:
3
1 2 1
Explanation:
Operation 1: Select the prefix of length 1 from the string A (= β01β). Flipping the prefix β0β modifies the string to β11β.
Operation 2: Select the prefix of length 2 from the string A (= β11β). Flipping the prefix β11β modifies the string to β00β.
Operation 3: Select the prefix of length 1 from the string A (= β00β). Flipping the prefix β0β to β1β modifies the string to β10β, which is the same as the string B.
Therefore, the total number of operations required is 3.Input: A = β0β, B = β1β
Output:
1
1
Approach: The given problem can be solved by fixing the bits one-by-one. To fix the ith bit, when A[i] and B[i] are unequal, flip the prefix of length i followed by flipping the prefix of length 1. Now, flip the prefix of length i. These three operations do not change any other bits in A. Perform these operations at all indices where A[i] is unequal B[i]. Since 3 operations are used per bit, overall 3 * N operations will be used.
In order to minimize the number of operations, the above approach can be modified by fixing the bits one by one in reverse order. To fix the ith bit, either the prefix of length i is required to be flipped or the first bit, and then the prefix of length i is required to be flipped. But in reverse order, the previously fixed bits do not get flipped again by this procedure and at most 2 operations are needed per bit. Therefore, the minimum number of operations required is 2*N.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum number // of operations required to convert // string a to another string b void minOperations(string a, string b, int n) { // Store the lengths of each // prefixes selected vector< int > ops; // Traverse the string for ( int i = n - 1; i >= 0; i--) { if (a[i] != b[i]) { // If first character // is same as b[i] if (a[0] == b[i]) { // Insert 1 to ops[] ops.push_back(1); // And, flip the bit a[0] = '0' + !(a[0] - '0' ); } // Reverse the prefix // string of length i + 1 reverse(a.begin(), a.begin() + i + 1); // Flip the characters // in this prefix length for ( int j = 0; j <= i; j++) { a[j] = '0' + !(a[j] - '0' ); } // Push (i + 1) to array ops[] ops.push_back(i + 1); } } // Print the number of operations cout << ops.size() << "\n" ; // Print the length of // each prefixes stored for ( int x : ops) { cout << x << ' ' ; } } // Driver Code int main() { string a = "10" , b = "01" ; int N = a.size(); minOperations(a, b, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to count minimum number // of operations required to convert // string a to another string b static void minOperations(String s1, String s2, int n) { char a[] = s1.toCharArray(); char b[] = s2.toCharArray(); // Store the lengths of each // prefixes selected ArrayList<Integer> ops = new ArrayList<>(); // Traverse the string for ( int i = n - 1 ; i >= 0 ; i--) { if (a[i] != b[i]) { // If first character // is same as b[i] if (a[ 0 ] == b[i]) { // Insert 1 to ops[] ops.add( 1 ); // And, flip the bit a[ 0 ] = (a[ 0 ] == '0' ? '1' : '0' ); } // Reverse the prefix // string of length i + 1 reverse(a, 0 , i); // Flip the characters // in this prefix length for ( int j = 0 ; j <= i; j++) { a[j] = (a[j] == '0' ? '1' : '0' ); } // Push (i + 1) to array ops[] ops.add(i + 1 ); } } // Print the number of operations System.out.println(ops.size()); // Print the length of // each prefixes stored for ( int x : ops) { System.out.print(x + " " ); } } // Function to reverse a[] // from start to end static void reverse( char a[], int start, int end) { while (start < end) { char temp = a[start]; a[start] = a[end]; a[end] = temp; start++; end--; } } // Driver code public static void main(String[] args) { String a = "10" , b = "01" ; int N = a.length(); minOperations(a, b, N); } } // This code is contributed by Kingash. |
Python3
# Python 3 program for the above approach # Function to count minimum number # of operations required to convert # string a to another string b def minOperations(a, b, n): # Store the lengths of each # prefixes selected ops = [] a = list (a) # Traverse the string for i in range (n - 1 , - 1 , - 1 ): if (a[i] ! = b[i]): # If first character # is same as b[i] if (a[ 0 ] = = b[i]): # Insert 1 to ops[] ops.append( 1 ) # And, flip the bit if ( ord (a[ 0 ]) - ord ( '0' )): a[ 0 ] = chr ( ord ( '0' ) + ord ( '0' )) else : a[ 0 ] = chr ( ord ( '0' ) + ord ( '1' )) # Reverse the prefix # string of length i + 1 a[:i + 1 ].reverse() # Flip the characters # in this prefix length for j in range (i + 1 ): if ( ord (a[j]) - ord ( '0' )): a[j] = chr ( ord ( '0' ) + ord ( '0' )) else : a[j] = chr ( ord ( '0' ) + ord ( '1' )) # Push (i + 1) to array ops[] ops.append(i + 1 ) # Print the number of operations print ( len (ops)) # Print the length of # each prefixes stored for x in ops: print (x, end = " " ) # Driver Code if __name__ = = "__main__" : a = "10" b = "01" N = len (a) minOperations(a, b, N) # This code is contributed by ukasp. |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to count minimum number // of operations required to convert // string a to another string b static void minOperations( string s1, string s2, int n) { char [] a = s1.ToCharArray(); char [] b = s2.ToCharArray(); // Store the lengths of each // prefixes selected List< int > ops = new List< int >(); // Traverse the string for ( int i = n - 1; i >= 0; i--) { if (a[i] != b[i]) { // If first character // is same as b[i] if (a[0] == b[i]) { // Insert 1 to ops[] ops.Add(1); // And, flip the bit a[0] = (a[0] == '0' ? '1' : '0' ); } // Reverse the prefix // string of length i + 1 reverse(a, 0, i); // Flip the characters // in this prefix length for ( int j = 0; j <= i; j++) { a[j] = (a[j] == '0' ? '1' : '0' ); } // Push (i + 1) to array ops[] ops.Add(i + 1); } } // Print the number of operations Console.WriteLine(ops.Count); // Print the length of // each prefixes stored foreach ( int x in ops) { Console.Write(x + " " ); } } // Function to reverse a[] // from start to end static void reverse( char [] a, int start, int end) { while (start < end) { char temp = a[start]; a[start] = a[end]; a[end] = temp; start++; end--; } } // Driver Code public static void Main() { string a = "10" , b = "01" ; int N = a.Length; minOperations(a, b, N); } } // This code is contributed by souravghosh0416. |
Javascript
<script> // JavaScript program to implement // the above approach // Function to count minimum number // of operations required to convert // string a to another string b function minOperations(s1, s2, n) { var a = s1.split( "" ); var b = s2.split( "" ); // Store the lengths of each // prefixes selected var ops = []; // Traverse the string for ( var i = n - 1; i >= 0; i--) { if (a[i] !== b[i]) { // If first character // is same as b[i] if (a[0] === b[i]) { // Insert 1 to ops[] ops.push(1); // And, flip the bit a[0] = a[0] === "0" ? "1" : "0" ; } // Reverse the prefix // string of length i + 1 reverse(a, 0, i); // Flip the characters // in this prefix length for ( var j = 0; j <= i; j++) { a[j] = a[j] === "0" ? "1" : "0" ; } // Push (i + 1) to array ops[] ops.push(i + 1); } } // Print the number of operations document.write(ops.length + "<br>" ); // Print the length of // each prefixes stored for (const x of ops) { document.write(x + " " ); } } // Function to reverse a[] // from start to end function reverse(a, start, end) { while (start < end) { var temp = a[start]; a[start] = a[end]; a[end] = temp; start++; end--; } } // Driver Code var a = "10" , b = "01" ; var N = a.length; minOperations(a, b, N); </script> |
3 1 2 1
Time Complexity: O(N2)
Auxiliary Space: O(N)