Given two binary strings s1[] and s2[] of the same length N, the task is to find the minimum number of operations to make them equal. Print -1 if it is impossible to do so. One operation is defined as choosing two adjacent indices of one of the binary string and inverting the characters at those positions, i.e, 1 to 0 and vice-versa.
Examples:
Input: s1[] = “0101”, s2[] = “1111”
Output: 2
Explanation: Invert the characters at 1 and 2 indices in the first string and at 0 and 1 indices in the second string to make them equal as 0011. There are other ways to do also like converting to 1111, etc.Input: s1[] = “011”, s2[] = “111”
Output: -1
Approach: The idea is to linearly traverse both strings and if at any index the characters are different than invert the ith and (i+1)th character in the string s1[]. Follow the steps below to solve the problem:
- Initialize the variable count as 0 to store the answer.
- Iterate over the range [0, N] using the variable i and perform the following steps:
- If s1[i] is not equal to s2[i], then do the following tasks:
- If s1[i] is equal to 1, then change it to 0, else, change it to 1.
- Similarly, if s1[i+1] is equal to 1, then change it to 0, else, change it to 1.
- Finally, increase the value of count by 1.
- If s1[i] is not equal to s2[i], then do the following tasks:
- If s1[] is equal to s2[], then return the value of count as the answer else return -1.
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 the minimum number // of inversions required. int find_Min_Inversion( int n, string s1, string s2) { // Initializing the answer int count = 0; // Iterate over the range for ( int i = 0; i < n - 1; i++) { if (s1[i] != s2[i]) { // If s1[i]!=s2[i], then inverse // the characters at i snd (i+1) // positions in s1. if (s1[i] == '1' ) { s1[i] = '0' ; } else { s1[i] = '1' ; } if (s1[i + 1] == '1' ) { s1[i + 1] = '0' ; } else { s1[i + 1] = '1' ; } // Adding 1 to counter // if characters are not same count++; } } if (s1 == s2) { return count; } return -1; } // Driver Code int main() { int n = 4; string s1 = "0101" ; string s2 = "1111" ; cout << find_Min_Inversion(n, s1, s2) << endl; return 0; } |
C
// C program for the above approach #include <stdio.h> #include <string.h> // Function to find the minimum number // of inversions required. int find_Min_Inversion( int n, char s1[1000], char s2[1000]) { // Initializing the answer int count = 0; // Iterate over the range for ( int i = 0; i < n - 1; i++) { if (s1[i] != s2[i]) { // If s1[i]!=s2[i], then inverse // the characters at i snd (i+1) // positions in s1. if (s1[i] == '1' ) { s1[i] = '0' ; } else { s1[i] = '1' ; } if (s1[i + 1] == '1' ) { s1[i + 1] = '0' ; } else { s1[i + 1] = '1' ; } // Adding 1 to counter // if characters are not same count++; } } if ( strcmp (s1, s2) != -1) { return count; } return -1; } // Driver Code int main() { int n = 4; char s1[1000] = "0101" ; char s2[1000] = "1111" ; printf ( "%d\n" , find_Min_Inversion(n, s1, s2)); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the minimum number // of inversions required. static int find_Min_Inversion( int n, char [] s1, char [] s2) { // Initializing the answer int count = 0 ; // Iterate over the range for ( int i = 0 ; i < n - 1 ; i++) { if (s1[i] != s2[i]) { // If s1[i]!=s2[i], then inverse // the characters at i snd (i+1) // positions in s1. if (s1[i] == '1' ) { s1[i] = '0' ; } else { s1[i] = '1' ; } if (s1[i + 1 ] == '1' ) { s1[i + 1 ] = '0' ; } else { s1[i + 1 ] = '1' ; } // Adding 1 to counter // if characters are not same count++; } } if (String.copyValueOf(s1).equals( String.copyValueOf(s2))) { return count; } return - 1 ; } // Driver Code public static void main(String[] args) { int n = 4 ; String s1 = "0101" ; String s2 = "1111" ; System.out.print( find_Min_Inversion(n, s1.toCharArray(), s2.toCharArray()) + "\n" ); } } // This code is contributed by umadevi9616 |
Python3
# Python 3 program for the above approach # Function to find the minimum number # of inversions required. def find_Min_Inversion(n, s1, s2): # Initializing the answer count = 0 # Iterate over the range s1 = list (s1) s2 = list (s2) for i in range (n - 1 ): if (s1[i] ! = s2[i]): # If s1[i]!=s2[i], then inverse # the characters at i snd (i+1) # positions in s1. if (s1[i] = = '1' ): s1[i] = '0' else : s1[i] = '1' if (s1[i + 1 ] = = '1' ): s1[i + 1 ] = '0' else : s1[i + 1 ] = '1' # Adding 1 to counter # if characters are not same count + = 1 s1 = ''.join(s1) s2 = ''.join(s2) if (s1 = = s2): return count return - 1 # Driver Code if __name__ = = '__main__' : n = 4 s1 = "0101" s2 = "1111" print (find_Min_Inversion(n, s1, s2)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG { // Function to find the minimum number // of inversions required. static int find_Min_Inversion( int n, char [] s1, char [] s2) { // Initializing the answer int count = 0; // Iterate over the range for ( int i = 0; i < n - 1; i++) { if (s1[i] != s2[i]) { // If s1[i]!=s2[i], then inverse // the characters at i snd (i+1) // positions in s1. if (s1[i] == '1' ) { s1[i] = '0' ; } else { s1[i] = '1' ; } if (s1[i + 1] == '1' ) { s1[i + 1] = '0' ; } else { s1[i + 1] = '1' ; } // Adding 1 to counter // if characters are not same count++; } } if ( new string (s1) == new string (s2)) { return count; } return -1; } // Driver Code public static void Main( string [] args) { int n = 4; string s1 = "0101" ; string s2 = "1111" ; // Function call Console.Write(find_Min_Inversion(n, s1.ToCharArray(), s2.ToCharArray()) + "\n" ); } } // This code is contributed by phasing17 |
Javascript
<script> // Java program for the above approach // Function to find the minimum number // of inversions required. function find_Min_Inversion(n, s1, s2) { // Initializing the answer let count = 0; // Iterate over the range for (let i = 0; i < n - 1; i++) { if (s1[i] != s2[i]) { // If s1[i]!=s2[i], then inverse // the characters at i snd (i+1) // positions in s1. if (s1[i] = '1' ) { s1[i] = '0' ; } else { s1[i] = '1' ; } if (s1[i + 1] = '1' ) { s1[i + 1] = '0' ; } else { s1[i + 1] = '1' ; } // Adding 1 to counter // if characters are not same count++; } } if (s1 != s2) { return count; } return -1; } // Driver Code let n = 4; let s1 = "0101" ; let s2 = "1111" ; document.write(find_Min_Inversion(n, s1, s2)); // This code is contributed by shivanisinghss2110 </script> |
2
Time Complexity: O(N), The time complexity is O(n), where n is the length of the strings s1 and s2. This is because the program iterates over the range of size n-1 once and performs constant time operations (comparisons and assignments) within each iteration.
Auxiliary Space: O(1), The space complexity is O(1), since the program only uses a constant amount of extra space regardless of the input size.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!