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 Codeint 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 Codeint 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 approachimport 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 Codeif __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 approachusing 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> |
Output:
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.
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!