Check If Two Binary Strings Can Be Made Equal by Swapping 1s Before 0s

In this article, we will be discussing an intriguing problem related to string manipulation and binary numbers in C++. The problem we will be tackling is "Check if two binary strings can be made equal by swapping 1s occurring before 0s". This problem is a great way to enhance your understanding of strings, binary numbers, and algorithmic thinking.

Problem Statement

The task is to determine if two binary strings can be made equal by swapping 1s that occur before 0s in the strings.

C++ Solution Approach

The approach to solve this problem is to keep track of the number of 1s and 0s in both strings. Two binary strings can be made equal by swapping 1s before 0s if and only if both strings have the same number of 1s and 0s.

Example

Here're the programs that implements this solution

#include <stdio.h>
#include <string.h>

int canBeMadeEqual(char *str1, char *str2) {
   int count1s_str1 = 0, count0s_str1 = 0;
   int count1s_str2 = 0, count0s_str2 = 0;

   // Count the number of '1's and '0's in str1
   for (int i = 0; str1[i] != '\0'; i++) {
      if (str1[i] == '1') {
         count1s_str1++;
      } else {
         count0s_str1++;
      }
   }

   // Count the number of '1's and '0's in str2
   for (int i = 0; str2[i] != '\0'; i++) {
      if (str2[i] == '1') {
         count1s_str2++;
      } else {
         count0s_str2++;
      }
   }

   // Compare the counts of '1's and '0's for both strings
   return count1s_str1 == count1s_str2 && count0s_str1 == count0s_str2;
}

int main() {
   char str1[] = "1100";
   char str2[] = "1010";
   int result = canBeMadeEqual(str1, str2);

   // Print the result based on whether the strings can be made equal or not
   printf(result ? "The binary strings can be made equal.\n" : "The binary strings cannot be made equal.\n");
   return 0;
}

The binary strings can be made equal.

#include <iostream>
#include <string>
using namespace std;

bool canBeMadeEqual(string str1, string str2) {
   int count1s_str1 = 0, count0s_str1 = 0;
   int count1s_str2 = 0, count0s_str2 = 0;
   
   for (char c : str1) {
      if (c == '1') {
         count1s_str1++;
      } else {
         count0s_str1++;
      }
   }
   
   for (char c : str2) {
      if (c == '1') {
         count1s_str2++;
      } else {
         count0s_str2++;
      }
   }
   
   return count1s_str1 == count1s_str2 && count0s_str1 == count0s_str2;
}

int main() {
   string str1 = "1100";
   string str2 = "1010";
   bool result = canBeMadeEqual(str1, str2);
   cout << (result ? "The binary strings can be made equal." : "The binary strings cannot be made equal.") << endl;
   return 0;
}

The binary strings can be made equal.

public class BinaryStringEquality {
   public static boolean canBeMadeEqual(String str1, String str2) {
      int count1s_str1 = 0, count0s_str1 = 0;
      int count1s_str2 = 0, count0s_str2 = 0;

      // Count the number of '1's and '0's in str1
      for (char c : str1.toCharArray()) {
         if (c == '1') {
            count1s_str1++;
         } else {
            count0s_str1++;
         }
      }

      // Count the number of '1's and '0's in str2
      for (char c : str2.toCharArray()) {
         if (c == '1') {
            count1s_str2++;
         } else {
            count0s_str2++;
         }
      }

      // Compare the counts of '1's and '0's for both strings
      return count1s_str1 == count1s_str2 && count0s_str1 == count0s_str2;
   }

   public static void main(String[] args) {
      String str1 = "1100";
      String str2 = "1010";
      boolean result = canBeMadeEqual(str1, str2);

      // Print the result based on whether the strings can be made equal or not
      System.out.println(result ? "The binary strings can be made equal." : "The binary strings cannot be made equal.");
   }
}

The binary strings can be made equal.

def can_be_made_equal(str1, str2):
   count1s_str1 = str1.count('1')
   count0s_str1 = str1.count('0')
   count1s_str2 = str2.count('1')
   count0s_str2 = str2.count('0')
   
   # Compare the counts of '1's and '0's for both strings
   return count1s_str1 == count1s_str2 and count0s_str1 == count0s_str2

def main():
   str1 = "1100"
   str2 = "1010"
   result = can_be_made_equal(str1, str2)
   
   # Print the result based on whether the strings can be made equal or not
   print("The binary strings can be made equal." if result else "The binary strings cannot be made equal.")

if __name__ == "__main__":
   main()

The binary strings can be made equal.

Explanation with a Test Case

Let's consider the binary strings "1100" and "1010".

When we pass these strings to the canBeMadeEqual function, it counts the number of 1s and 0s in both strings.

In the string "1100", there are 2 ones and 2 zeros. In the string "1010", there are also 2 ones and 2 zeros.

Since the number of 1s and 0s in both strings is equal, the function returns true, indicating that the strings can be made equal by swapping 1s before 0s.

Conclusion

This problem presents a great way to apply knowledge of string manipulation and binary numbers to solve a complex problem in C++. It's an excellent problem to practice your C++ coding skills and to understand how to work with binary numbers in string format.