String transformation using XOR and OR
Given two binary strings. The task is to check if string s1 can be converted to string s2 by performing the given operations any number of times.
- Choose any two adjacent characters in a string s1 and replace one of them by a^b and the other by a b (a OR b).
Examples:
Input: S1 = “11”, S2 = “10”
Output: YES
Select two adjacent characters and replace s2[0] by s1[0]s1[1] and
change s2[1] by s1[0]^s1[1]Input: S1 = “000”, S2 = “101”
Output: NO
Approach: Given below is a table that explains all the possibilities of XOR and OR operations.
X | Y | X^Y | XY |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
If both the string consists of 0’s only and their length is same, conversion is possible, as two adjacent zero will result in zeros only, irrespective of the operation done on it. If both the string have 1’s, follow the steps below to check if String1 can be converted to String2.
- Check if lengths are equal or not
- Check if both the strings have a minimum of one 1, as all the conversions are possible if both the strings have at least 1 which can be seen in the table
If both of the above conditions are true, it is possible to convert String1 can be converted to String2.
Below is the implementation of the above approach:
C++
// C++ program to check if string1 can be // converted to string2 using XOR and OR operations #include <bits/stdc++.h> using namespace std; // function to check if conversion is possible or not bool solve(string s1, string s2) { bool flag1 = 0, flag2 = 0; // if lengths are different if (s1.length() != s2.length()) return false ; int l = s1.length(); // iterate to check if both strings have 1 for ( int i = 0; i < l; i++) { // to check if there is // even one 1 in string s1 if (s1[i] == '1' ) flag1 = 1; // to check if there is even // one 1 in string s2 if (s2[i] == '1' ) flag2 = 1; if (flag1 && flag2) return true ; } //if both strings have only '0' if (!flag1&&!flag2) return true ; // if both string do not have a '1'. return false ; } // Driver code int main() { string s1 = "100101" ; string s2 = "100000" ; if (solve(s1, s2)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program to check if // string1 can be converted // to string2 using XOR and // OR operations import java.io.*; import java.util.*; class GFG { // function to check if // conversion is possible // or not static boolean solve(String s1, String s2) { boolean flag1 = false , flag2 = false ; // if lengths are different if (s1.length() != s2.length()) return false ; int l = s1.length(); // iterate to check if // both strings have 1 for ( int i = 0 ; i < l; i++) { // to check if there is // even one 1 in string s1 if (s1.charAt(i) == '1' ) flag1 = true ; // to check if there is even // one 1 in string s2 if (s2.charAt(i) == '1' ) flag2 = true ; if (flag1 == true && flag2 == true ) return true ; } //if both strings have only '0' if (!flag1&&!flag2) return true ; // if both string do // not have a '1'. return false ; } // Driver code public static void main(String args[]) { String s1 = "100101" ; String s2 = "100000" ; if (solve(s1, s2) == true ) System.out.print( "Yes" ); else System.out.print( "No" ); } } |
Python3
# Python3 program to check # if string1 can be converted # to string2 using XOR and # OR operations # function to check if # conversion is possible or not def solve(s1, s2): flag1 = 0 flag2 = 0 # if lengths are different if ( len (s1) ! = len (s2)): return False l = len (s1) # iterate to check if # both strings have 1 for i in range ( 0 , l): # to check if there is # even one 1 in string s1 if (s1[i] = = '1' ): flag1 = 1 ; # to check if there is even # one 1 in string s2 if (s2[i] = = '1' ): flag2 = 1 # if both string # do not have a '1'. if (flag1 & flag2): return True if (!flag1 & !flag2): return True return False # Driver code s1 = "100101" s2 = "100000" if solve(s1, s2): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by Shivi_Aggarwal |
C#
// C# program to check if // string1 can be converted // to string2 using XOR and // OR operations using System; class GFG { // function to check if // conversion is possible // or not static bool solve(String s1, String s2) { bool flag1 = false , flag2 = false ; // if lengths are different if (s1.Length != s2.Length) return false ; int l = s1.Length; // iterate to check if // both strings have 1 for ( int i = 0; i < l; i++) { // to check if there is // even one 1 in string s1 if (s1[i] == '1' ) flag1 = true ; // to check if there is even // one 1 in string s2 if (s2[i] == '1' ) flag2 = true ; if (flag1 == true && flag2 == true ) return true ; } //if both strings have only '0' if (!flag1&&!flag2) return true ; // if both string do // not have a '1'. return false ; } // Driver code public static void Main() { String s1 = "100101" ; String s2 = "100000" ; if (solve(s1, s2) == true ) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // PHP program to check if string1 // can be converted to string2 // using XOR and OR operations // function to check if conversion // is possible or not function solve( $s1 , $s2 ) { // if lengths are different if ( strlen ( $s1 ) != strlen ( $s2 )) return false; $l = strlen ( $s1 ); // iterate to check if // both strings have 1 for ( $i = 0; $i < 1; $i ++) { // to check if there is // even one 1 in string s1 if ( $s1 [ $i ] == '1' ) $flag1 = 1; // to check if there is even // one 1 in string s2 if ( $s2 [ $i ] == '1' ) $flag2 = 1; if (! $flag1 && ! $flag2 ) return true; } // if both string do // not have a '1'. return false; } // Driver code $s1 = "100101" ; $s2 = "100000" ; if (solve( $s1 , $s2 )) echo ( "Yes" ); else echo ( "No" ); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript program to check if string1 can be // converted to string2 using XOR and OR operations // function to check if conversion is possible or not function solve(s1, s2) { let flag1 = 0, flag2 = 0; // if lengths are different if (s1.length != s2.length) return false ; let l = s1.length; // iterate to check if both strings have 1 for (let i = 0; i < l; i++) { // to check if there is // even one 1 in string s1 if (s1[i] == '1' ) flag1 = 1; // to check if there is even // one 1 in string s2 if (s2[i] == '1' ) flag2 = 1; if (flag1 && flag2) return true ; } //if both strings have only '0' if (!flag1&&!flag2) return true ; // if both string do not have a '1'. return false ; } // Driver code let s1 = "100101" ; let s2 = "100000" ; if (solve(s1, s2)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output
Yes
Time Complexity: O(n) where n is the length of input strings.
Auxiliary Space: O(1), no extra space is required, so it is a constant.