Count valid Bitwise operation combinations for Binary Strings
Given an odd integer N (N >= 3), a binary string S of length N and another string O of length (N-1)/2. Here, each character in string O can be one of the following: β&β, β|β or β^β representing Bitwise operations AND, OR, and XOR respectively, the task is to find the number of possible combinations for string O that satisfies the following conditions:
- S[2] = S[0] O[0] S[1]
- S[4] = S[2] O[1] S[3]
- S[6] = S[4] O[2] S[5]
- And so on, up to the last valid index of S.
Note: Output can be very large so modulo it by (10^9 + 7).
Examples:
Input: β110β
Output: 1
Explanation: The only operation string that satisfies the conditions is β^β. S[0] ^ S[1] = S[2], that is 1 ^ 1 = 0Input: β10101β³
Output: 4
Explanation: There can be four possible strings. They are:
- β^^β : S[0] ^ S[1] = S[2], that is 1 ^ 0 = 1 and S[2] ^ S[3] = S[4], that is 1 ^ 0 = 1
- β^|β : S[0] ^ S[1] = S[2], that is 1 ^ 0 = 1 and S[2] | S[3] = S[4], that is 1 | 0 = 1
- β|^β : S[0] | S[1] = S[2], that is 1 | 0 = 1 and S[2] ^ S[3] = S[4], that is 1 ^ 0 = 1
- β||β : S[0] | S[1] = S[2], that is 1 | 0 = 1 and S[2] | S[3] = S[4], that is 1 | 0 = 1
Approach: To solve the problem follow the below idea:
The problem can be solved by using a combination based approach where at every index i (i >= 2 and i is odd), we multiply our answer with the number of possible operators which we can use between S[i-2] and S[i-1] to get S[i]. Suppose, if at any index i, the possible operators are β^β and β&β, then we multiply our answer with 2 and so on.
Below are the steps to solve the problem:
- Initialize a variable ans = 1 to store the number of possible strings for O.
- Iterate over the string S starting from index i = 2.
- Maintain a variable cnt = 0, to count the number of possible operators for that index.
- Check if we can use Bitwise AND for this iteration. If yes, increment cnt by 1.
- Check if we can use Bitwise OR for this iteration. If yes, increment cnt by 1.
- Check if we can use Bitwise XOR for this iteration. If yes, increment cnt by 1.
- Multiply ans by cnt.
- Increment index i by 2.
- Return ans to get the number of all possible combinations for string O.
Below is the implementation for the above approach:
C++
// C++ Code for the above approach: #include <bits/stdc++.h> using namespace std; // MOD value const int MOD = 1e9 + 7; // Function to process the string long long getCount(string s) { // Variable to store the number of // possible strings O long long ans = 1; // Iterate over string S starting // from index 2 for ( int i = 2; i < s.length(); i += 2) { // Store the operands as integers int x = s[i - 2] - '0' ; int y = s[i - 1] - '0' ; int z = s[i] - '0' ; // We need every equation as x # y = z // where # is any operator of {&, |, ^} // Variable to store the number of // valid operators int cnt = 0; // Bitwise-and '&' cnt += (x & y) == z; // Bitwise-or '|' cnt += (x | y) == z; // Bitwise-xor '^' cnt += (x ^ y) == z; // Combinations of the operators ans *= cnt; ans %= MOD; } return ans; } // Drivers code int main() { string s1 = "110"; string s2 = "10101"; // Function call to get the // count of strings cout << getCount(s1) << '\n' ; cout << getCount(s2) << '\n' ; return 0; } |
Java
// Java Code for the above approach import java.io.*; import java.util.*; public class GFG { // MOD value static final int MOD = 1000000007 ; // Function to process the string static long getCount(String s) { // variable to store the number of // possible strings O long ans = 1 ; // Iterate over the string S starting // from index 2 for ( int i = 2 ; i < s.length(); i += 2 ) { // Store the operands as ints int x = s.charAt(i - 2 ) - '0' ; int y = s.charAt(i - 1 ) - '0' ; int z = s.charAt(i) - '0' ; // We need every equation as x # y = z // where # is any operator of {&, |, ^} // variable to store the number of // valid operators int cnt = 0 ; // Bitwise-and '&' cnt += ((x & y) == z) ? 1 : 0 ; // Bitwise-or '|' cnt += ((x | y) == z) ? 1 : 0 ; // Bitwise-xor '^' cnt += ((x ^ y) == z) ? 1 : 0 ; // Combinations of the operators ans *= cnt; ans %= MOD; } return ans; } public static void main(String[] args) { String s1 = " 110 "; String s2 = " 10101 "; // Function call to get the // count of strings System.out.println(getCount(s1)); System.out.println(getCount(s2)); } } |
Python3
# Python Code for the above approach: MOD = 10 * * 9 + 7 # Function to process the string def get_count(s): # variable to store the number of # possible strings O ans = 1 # Iterate over the string S starting # from index 2 for i in range ( 2 , len (s), 2 ): # Store the operands as ints x = int (s[i - 2 ]) y = int (s[i - 1 ]) z = int (s[i]) # We need every equation as x # y = z # where # is any operator of {&, |, ^} # variable to store the number of # valid operators cnt = 0 # Bitwise-and '&' cnt + = (x & y) = = z # Bitwise-or '|' cnt + = (x | y) = = z # Bitwise-xor '^' cnt + = (x ^ y) = = z # Combinations of the operators ans * = cnt ans % = MOD return ans s1 = " 110 " s2 = " 10101 " # Function call to get the count of strings print (get_count(s1)) print (get_count(s2)) |
C#
// C# Code for the above approach using System; public class GFG { // MOD value const int MOD = 1000000007; // Function to process the string static long getCount( string s) { // variable to store the number of // possible strings O long ans = 1; // Iterate over the string S starting // from index 2 for ( int i = 2; i < s.Length; i += 2) { // Store the operands as ints int x = s[i - 2] - '0' ; int y = s[i - 1] - '0' ; int z = s[i] - '0' ; // We need every equation as x # y = z // where # is any operator of {&, |, ^} // variable to store the number of // valid operators int cnt = 0; // Bitwise-and '&' cnt += ((x & y) == z) ? 1 : 0; // Bitwise-or '|' cnt += ((x | y) == z) ? 1 : 0; // Bitwise-xor '^' cnt += ((x ^ y) == z) ? 1 : 0; // Combinations of the operators ans *= cnt; ans %= MOD; } return ans; } public static void Main() { string s1 = "110" ; string s2 = "10101" ; // Function call to get the // count of strings Console.WriteLine(getCount(s1)); Console.WriteLine(getCount(s2)); } } // This code is contributed by ragul21 |
Javascript
// Javascript Code for the above approach: // Function to process the string function getCount(s) { // Variable to store the number of possible strings O let ans = 1; // Iterate over the string S starting from index 2 for (let i = 2; i < s.length; i += 2) { // Store the operands as integers const x = parseInt(s[i - 2]); const y = parseInt(s[i - 1]); const z = parseInt(s[i]); // We need every equation as x # y = z // where # is any operator of {&, |, ^} // Variable to store the number of valid operators let cnt = 0; // Bitwise-and '&' cnt += (x & y) === z ? 1 : 0; // Bitwise-or '|' cnt += (x | y) === z ? 1 : 0; // Bitwise-xor '^' cnt += (x ^ y) === z ? 1 : 0; // Combinations of the operators ans *= cnt; ans %= 1000000007; // MOD value } return ans; } const s1 = "110" ; const s2 = "10101" ; // Function call to get the count of strings console.log(getCount(s1)); console.log(getCount(s2)); |
1 4
Time Complexity: O(N), where N is the length of string S.
Auxiliary Space: O(1)