Count different Bitwise OR values of equal length strings S1 and S2 by swapping exactly one pair of characters from the first string
Given two binary strings S1 and S2, both of length N, the task is to count the number of different values of Bitwise OR other than the Bitwise OR of the original strings S1 and S2 by swapping exactly one pair of characters from the string S1.
Examples:
Input: S1 = β1100β, S2 = β0011β
Output: 4
Explanation: Bitwise OR of S1 and S2, if no swapping is performed is β1111β.
Below are swapping of characters performed to get the different values of Bitwise OR:
- If the characters at 0th and 2nd index are swapped, then string S1 modifies to β0110β. Now, the Bitwise OR of both the string is β0111β.
- If the characters at 0th and 3rd index are swapped, then string S1 modifies to β0101β. Now, the Bitwise OR of both the string isβ0111β³.
- If the characters at 1st and 2nd index are swapped, then string S1 modifies to β1010β. Now, the Bitwise OR of both the string is β1011β.
- If the characters at 1st and 3rd index are swapped, then string S1 modifies to β1001β. Now, the Bitwise OR of both the string isβ1011β³.
After the above steps, all the Bitwise-OR are different from the Bitwise OR of the original string. Therefore, the total count is 4.
Input: S1 = β01001β, S2 = β11011β
Output: 2
Approach: The given problem can be solved based on the following observations:
- If the same character is swapped in the string S1, then it will not affect the bitwise OR.
- If the different characters are swapped in the string S1 let say S1[i] = β0β and S2[j] = β1β then the bitwise OR of the value is changed as per the following rules:
- If S2[i] = β0β and S2[j] = β0β.
- If S2[i] = β1β and S2[j] = β0β.
- If S2[i] = β0β and S2[j] = β1β.
From the above observations, Follow the below steps to solve the problem:
- Initialize four variable, say t00, t10, t11, t01 that stores the number of indexes i such that S1[i] = β0β and S2[i] = β0β, S1[i] = β1β and S2[i] = β0β, S1[i] = β1β and S2[i] = β1β, and S1[i] = β0β and S2[i] = β1β respectively.
- Traverse the given strings S1 and S2, and increment the value of t00, t10, t11, t01 as per the following:
- If S1[i] = β0β and S2[i] =β0β², then increment the value of t00 by 1.
- If S1[i] = β1β and S2[i] = β0β, then increment the value of t10 by 1.
- If S1[i] = β1β and S2[i] = β1β, then increment the value of t11 by 1.
- If S1[i] = β0β and S2[i] = β1β, then increment the value of t01 by 1.
- After completing the above steps, print the value of t00 * t10 + t01 * t10 + t00 * t11 as the resultant number of swaps required having different Bitwise OR from the original Bitwise OR.
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 number of ways // to obtain different Bitwise OR void differentBitwiseOR(string s1, string s2) { int n = s1.size(); // Stores the count of pairs t00, // t10, t01, t11 int t00 = 0, t10 = 0, t01 = 0, t11 = 0; // Traverse the characters of // the string S1 and S2 for ( int i = 0; i < n; i++) { // Count the pair (0, 0) if (s1[i] == '0' && s2[i] == '0' ) { t00++; } // Count the pair (1, 0) if (s1[i] == '1' && s2[i] == '0' ) { t10++; } // Count the pair (1, 1) if (s1[i] == '1' && s2[i] == '1' ) { t11++; } // Count the pair (0, 1) if (s1[i] == '0' && s2[i] == '1' ) { t01++; } } // Number of ways to calculate the // different bitwise OR int ans = t00 * t10 + t01 * t10 + t00 * t11; // Print the result cout << ans; } // Driver Code int main() { string S1 = "01001" ; string S2 = "11011" ; differentBitwiseOR(S1, S2); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the number of ways // to obtain different Bitwise OR static void differentBitwiseOR(String s1, String s2) { int n = s1.length(); // Stores the count of pairs t00, // t10, t01, t11 int t00 = 0 , t10 = 0 , t01 = 0 , t11 = 0 ; // Traverse the characters of // the string S1 and S2 for ( int i = 0 ; i < n; i++) { // Count the pair (0, 0) if (s1.charAt(i) == '0' && s2.charAt(i) == '0' ) { t00++; } // Count the pair (1, 0) if (s1.charAt(i) == '1' && s2.charAt(i) == '0' ) { t10++; } // Count the pair (1, 1) if (s1.charAt(i) == '1' && s2.charAt(i) == '1' ) { t11++; } // Count the pair (0, 1) if (s1.charAt(i) == '0' && s2.charAt(i) == '1' ) { t01++; } } // Number of ways to calculate the // different bitwise OR int ans = t00 * t10 + t01 * t10 + t00 * t11; // Print the result System.out.print(ans); } // Driver Code public static void main(String[] args) { String S1 = "01001" ; String S2 = "11011" ; differentBitwiseOR(S1, S2); } } // This code is contributed by subhammahato348 |
Python3
# Python program for the above approach # Function to find the number of ways # to obtain different Bitwise OR def differentBitwiseOR(s1, s2): n = len (s1) # Stores the count of pairs t00, # t10, t01, t11 t00 = 0 t10 = 0 t01 = 0 t11 = 0 # Traverse the characters of # the string S1 and S2 for i in range (n): # Count the pair (0, 0) if (s1[i] = = '0' and s2[i] = = '0' ): t00 + = 1 # Count the pair (1, 0) if (s1[i] = = '1' and s2[i] = = '0' ): t10 + = 1 # Count the pair (1, 1) if (s1[i] = = '1' and s2[i] = = '1' ): t11 + = 1 # Count the pair (0, 1) if (s1[i] = = '0' and s2[i] = = '1' ): t01 + = 1 # Number of ways to calculate the # different bitwise OR ans = t00 * t10 + t01 * t10 + t00 * t11 # Print the result print (ans) # Driver Code S1 = "01001" S2 = "11011" differentBitwiseOR(S1, S2) # This code is contributed by _saurabh_jaiswal |
C#
// C# program for the above approach using System; class GFG{ // Function to find the number of ways // to obtain different Bitwise OR static void differentBitwiseOR(String s1, String s2) { int n = s1.Length; // Stores the count of pairs t00, // t10, t01, t11 int t00 = 0, t10 = 0, t01 = 0, t11 = 0; // Traverse the characters of // the string S1 and S2 for ( int i = 0; i < n; i++) { // Count the pair (0, 0) if (s1[i] == '0' && s2[i] == '0' ) { t00++; } // Count the pair (1, 0) if (s1[i] == '1' && s2[i] == '0' ) { t10++; } // Count the pair (1, 1) if (s1[i] == '1' && s2[i] == '1' ) { t11++; } // Count the pair (0, 1) if (s1[i] == '0' && s2[i] == '1' ) { t01++; } } // Number of ways to calculate the // different bitwise OR int ans = t00 * t10 + t01 * t10 + t00 * t11; // Print the result Console.Write(ans); } // Driver Code public static void Main() { String S1 = "01001" ; String S2 = "11011" ; differentBitwiseOR(S1, S2); } } // This code is contributed by subhammahato348 |
Javascript
<script> // JavaScript program for the above approach // Function to find the number of ways // to obtain different Bitwise OR function differentBitwiseOR(s1, s2) { let n = s1.length; // Stores the count of pairs t00, // t10, t01, t11 let t00 = 0, t10 = 0, t01 = 0, t11 = 0; // Traverse the characters of // the string S1 and S2 for (let i = 0; i < n; i++) { // Count the pair (0, 0) if (s1[i] == '0' && s2[i] == '0' ) { t00++; } // Count the pair (1, 0) if (s1[i] == '1' && s2[i] == '0' ) { t10++; } // Count the pair (1, 1) if (s1[i] == '1' && s2[i] == '1' ) { t11++; } // Count the pair (0, 1) if (s1[i] == '0' && s2[i] == '1' ) { t01++; } } // Number of ways to calculate the // different bitwise OR let ans = t00 * t10 + t01 * t10 + t00 * t11; // Print the result document.write(ans); } // Driver Code let S1 = "01001" ; let S2 = "11011" ; differentBitwiseOR(S1, S2); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us