Given binary strings S1 and S2 of length N, the task is to check if S2 can be made equal to S1 by performing the following operations on S2:
- The first operation is Si = Si ? Si+1. ( ? is the XOR operation)
- The second operation is Si+1 = Si+1 ? Si.
Examples:
Input: S1 = “00100”, S2 = “00011”
Output: Yes
?Explanation: We can apply the following operations on S2 :
1. Select i = 2, So the conversion is 00011 ? 00111
2. Select i = 3. So the conversion is 00111 ? 00100.
Hence it is possible to make S2 equal to S1 by applying the above operation on index 2 and 3.Input: S1 = “10101”, S2 = “01000”
?Output: No
Approach: The problem can be solved based on the following observation:
The operations have the following effects:
- 01 becomes 11
- 10 becomes 11
- 00 becomes 00
- 11 becomes 00
Let’s get the easy cases out of the way:
- If S2 = S1, the answer is YES
- If S2 is 000…00 (i.e S2 does not have a 1), then we can only perform the operation and it will be the third case shown above, which does not change anything. Therefore, the answer is NO if S2 ? S1.
- Now, assume S2 ? S1 and S2 has a 1. It is possible to convert S2 to S1 if and only if S1 has at least two consecutive same characters.
Follow the steps mentioned below to implement the above idea:
- Check if the strings are already equal to each other. If so, then return true.
- Otherwise, check if S2 has at least one ‘1’:
- If it has, then check for the condition that S1 has at least two consecutive same characters.
- If the above condition is satisfied then return true.
- Otherwise, return false.
Below is the implementation of the above approach.
C++
// c++ code to implement the approach #include <iostream> using namespace std; // Function to check whether S2 can be made equal // to S1 after performing given operations void checkEqual(string S1, string S2, int n) { int c_1 = 0; int c_2 = 0; if (S2==S1) { cout << "Yes" ; } for ( int j = 0; j < n; j++) { if (S2[j] == '1' ) { c_1++; } if (S1[j] == '1' ) { c_2++; } } if (c_1 == 0 && c_2 > 0) { cout << "No" ; } int c = 0; for ( int k = 0; k < n - 1; k++) { if (S1[k] != S1[k + 1]) { c++; } } if (c == n - 1) { cout << "No" ; } else { cout << "Yes" ; } } int main() { string S1 = "00100" ; string S2 = "00011" ; int N = S1.length(); // Function call checkEqual(S1, S2, N); return 0; } //this code is contributed by aditya942003patil |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to check whether S2 can be made equal // to S1 after performing given operations public static void checkEqual(String S1, String S2, int n) { char [] a = S2.toCharArray(); char [] b = S1.toCharArray(); int c_1 = 0 ; int c_2 = 0 ; if (String.valueOf(a).equals(String.valueOf(b))) { System.out.println( "Yes" ); } for ( int j = 0 ; j < n; j++) { if (a[j] == '1' ) { c_1++; } if (b[j] == '1' ) { c_2++; } } if (c_1 == 0 && c_2 > 0 ) { System.out.println( "No" ); } int c = 0 ; for ( int k = 0 ; k < n - 1 ; k++) { if (b[k] != b[k + 1 ]) { c++; } } if (c == n - 1 ) { System.out.println( "No" ); } else { System.out.println( "Yes" ); } } // Driver code public static void main(String[] args) { String S1 = "00100" ; String S2 = "00011" ; int N = S1.length(); // Function call checkEqual(S1, S2, N); } } |
Python3
# python code to implement the approach # Function to check whether S2 can be made equal # to S1 after performing given operations def checkEqual(S1, S2, n): c_1 = 0 c_2 = 0 if (S2 = = S1): print ( "yes" ) for j in range (n): if (S2[j] = = '1' ): c_1 + = 1 if (S1[j] = = '1' ): c_2 + = 1 if (c_1 = = 0 and c_2 > 0 ): print ( "No" ) c = 0 for k in range (n - 1 ): if (S1[k] ! = S1[k + 1 ]): c + = 1 if (c = = n - 1 ): print ( "No" ) else : print ( "yes" ) S1 = "00100" S2 = "00011" N = len (S1) # Function call checkEqual(S1, S2, N); # This code is contributed by Atul_kumar_Shrivastava |
C#
// C# code to implement the approach using System; public class GFG { // Function to check whether S2 can be made equal // to S1 after performing given operations public static void checkEqual(String S1, String S2, int n) { char [] a = S2.ToCharArray(); char [] b = S1.ToCharArray(); int c_1 = 0; int c_2 = 0; if (String.Join( "" ,a).Equals(String.Join( "" ,b))) { Console.WriteLine( "Yes" ); } for ( int j = 0; j < n; j++) { if (a[j] == '1' ) { c_1++; } if (b[j] == '1' ) { c_2++; } } if (c_1 == 0 && c_2 > 0) { Console.WriteLine( "No" ); } int c = 0; for ( int k = 0; k < n - 1; k++) { if (b[k] != b[k + 1]) { c++; } } if (c == n - 1) { Console.WriteLine( "No" ); } else { Console.WriteLine( "Yes" ); } } // Driver code public static void Main(String[] args) { String S1 = "00100" ; String S2 = "00011" ; int N = S1.Length; // Function call checkEqual(S1, S2, N); } } // This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript program of above approach. // Function to check whether S2 can be made equal // to S1 after performing given operations function checkEqual(S1, S2, n) { let a = S2.split(); let b = S1.split(); let c_1 = 0; let c_2 = 0; if (a == b) { document.write( "Yes" ); } for (let j = 0; j < n; j++) { if (a[j] == '1' ) { c_1++; } if (b[j] == '1' ) { c_2++; } } if (c_1 == 0 && c_2 > 0) { document.write( "No" ); } let c = 0; for (let k = 0; k < n - 1; k++) { if (b[k] != b[k + 1]) { c++; } } if (c == n - 1) { document.write( "No" ); } else { document.write( "Yes" ); } } // Driver code let S1 = "00100" ; let S2 = "00011" ; let N = S1.length; // Function call checkEqual(S1, S2, N); // This code is contributed by sanjoy_62. </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!