Given two binary string M and N of equal length, the task is to find a minimum number of operations (swaps) required to convert string N to M.
Examples:
Input: str1 = "1101", str2 = "1110" Output: 1 Swap last and second last element in the binary string, so that it become 1101 Input: str1 = "1110000", str2 = "0001101" Output: 3
Approach:
Initialize the counter and Iterate over the M such that if any non-equal elements found in both binary strings, increment the counter. In the end, if the counter is even then print the result/2 because for one swap two elements are non-identical.
Suppose S1 = “10” and S2 = “01”, so two pairs are non-identical, the count = 2 and as the count is even, so number of swaps are count/2, i.e. 1. Even count determines that there are chances to swap the elements.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Method to count swapsvoid minSwaps(string str1, string str2){ // Initialize the count int count = 0; // Iterate the loop with str1 length for (int i = 0; i < str1.length(); i++) { // If any non-equal elements are found // increment the counter if (str1[i] != str2[i]) count++; } // If counter is even print the swap if (count % 2 == 0) cout << count / 2; else cout << "Not Possible";}// Driver codeint main(){ // Take two input string binaryString1 = "1110000"; string binaryString2 = "0001101"; // Call the method minSwaps(binaryString1, binaryString2); return 0;} |
Java
// Java Program to count minimum number of swap// required to make string N to Mpublic class GFG { // Method to count swaps static void minSwaps(String str1, String str2) { // Initialize the count int count = 0; // Iterate the loop with str1 length for (int i = 0; i < str1.length(); i++) { // If any non-equal elements are found // increment the counter if (str1.charAt(i) != str2.charAt(i)) count++; } // If counter is even print the swap if (count % 2 == 0) System.out.println(count / 2); else System.out.println("Not Possible"); } // Driver Code public static void main(String args[]) { // Take two input String binaryString1 = "1110000"; String binaryString2 = "0001101"; // Call the method minSwaps(binaryString1, binaryString2); }} |
Python 3
# Python3 implementation of # the above approach # function to count swapsdef minSwaps(str1, str2) : # Initialize the count count = 0 # Iterate the loop with # length of str1 for i in range(len(str1)) : # If any non-equal elements are # found increment the counter if str1[i] != str2[i] : count += 1 # If counter is even print # the swap if count % 2 == 0 : print(count // 2) else : print("Not Possible")# Driver codeif __name__ == "__main__" : # Take two input binaryString1 = "1110000" binaryString2 = "0001101" # Call the function minSwaps( binaryString1, binaryString2)# This code is contributed by ANKITRAI1 |
C#
// C# Program to count minimum number of swap// required to make string N to Musing System;class GFG{// Method to count swapsstatic void minSwaps(string str1, string str2){ // Initialize the count int count = 0; // Iterate the loop with str1 length for (int i = 0; i < str1.Length; i++) { // If any non-equal elements are found // increment the counter if (str1[i] != str2[i]) count++; } // If counter is even print the swap if (count % 2 == 0) Console.WriteLine(count / 2); else Console.WriteLine("Not Possible");}// Driver Codepublic static void Main(){ // Take two input string binaryString1 = "1110000"; string binaryString2 = "0001101"; // Call the method minSwaps(binaryString1, binaryString2);}}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php// PHP implementation of the above // approach // Method to count swaps function minSwaps($str1, $str2) { // Initialize the count $count = 0; // Iterate the loop with str1 length for ($i = 0; $i < strlen($str1); $i++) { // If any non-equal elements are // found increment the counter if ($str1[$i] != $str2[$i]) $count++; } // If counter is even print the swap if ($count % 2 == 0) echo ($count / 2); else echo "Not Possible"; } // Driver code // Take two input $binaryString1 = "1110000"; $binaryString2 = "0001101"; // Call the method minSwaps($binaryString1, $binaryString2); // This code is contributed// by Sach_Code?> |
Javascript
<script> // JavaScript Program to count minimum number of swap // required to make string N to M // Method to count swaps function minSwaps(str1, str2) { // Initialize the count var count = 0; // Iterate the loop with str1 length for (var i = 0; i < str1.length; i++) { // If any non-equal elements are found // increment the counter if (str1[i] !== str2[i]) count++; } // If counter is even print the swap if (count % 2 === 0) document.write(count / 2); else document.write("Not Possible"); } // Driver Code // Take two input var binaryString1 = "1110000"; var binaryString2 = "0001101"; // Call the method minSwaps(binaryString1, binaryString2); </script> |
Output
3
Time Complexity: O(n)
Auxiliary Space: O(1) it is using constant space for variables
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!
