Given an array of characters arr[] of size N, whose each character is either ‘&’ (Bitwise AND) or ‘|’ (Bitwise OR). there are many possible ways of having a binary array of size N+1. Any of these arrays (say X[]) is transformed to another array Y[] by performing the following operations
- Y[0] = X[0].
- for every i ( i from 1 to N-1) Y[i] = (Y[i – 1] & X[i]) if arr[i – 1] is ‘&’ and Y[i] = (Y[i – 1] | X[i]) if arr[i – 1] is ‘|’.
The task is to find how many arrays are there which can be transformed to array Y[] such that the last element is 1.
Examples :
Input: arr[] = {‘& ‘, ‘|’}
Output: 5
Explanation: N = 2, we have eight possible binary arrays of size N + 1, ( {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0}, {0, 1, 1}, {1, 0, 1}, {1, 1, 0} and {1, 1, 1} )
we will transform each of them into Y by the above rules and check whether they end with 1 or 0. If they end with 1 that means they will be counted in our answer.
array 1: X = {0, 0, 0}
Y[0] = X[0] = 0
Y[1] = Y[0] & X[1] = 0 & 0 = 0
Y[2] = Y[1] | X[2] = 0 | 0 = 0
Finally, Y for X is {0, 0, 0} as it does not end with 1 it will not be counted in our answer.
array 2: X = {0, 0, 1}
Y[0] = X[0] = 0
Y[1] = Y[0] & X[1] = 0 & 0 = 0
Y[2] = Y[1] | X[2] = 0 | 1 = 1
Finally, Y for X is {0, 0, 1} as it ends with 1 it will be counted in our answer.
array 3: X = {0, 1, 0}
Y[0] = X[0] = 0
Y[1] = Y[0] & X[1] = 0 & 1 = 0
Y[2] = Y[1] | X[2] = 0 | 0 = 0
Finally, Y for X is {0, 0, 0} as it does not end with 1 it will not be counted in our answer.
array 4: X = {1, 0, 0}
Y[0] = X[0] = 1
Y[1] = Y[0] & X[1] = 1 & 0 = 0
Y[2] = Y[1] | X[2] = 0 | 0 = 0
Finally Y for X is {1, 0, 0} as it does not end with 1 it will not be counted in our answer.
array 5: X = {0, 1, 1}
Y[0] = X[0] = 0
Y[1] = Y[0] & X[1] = 0 & 1 = 0
Y[2] = Y[1] | X[2] = 0 | 1 = 1
Finally Y for X is {0, 0, 1} as it end with 1 it will be counted in our answer.
array 6: X = {1, 0, 1}
Y[0] = X[0] = 1
Y[1] = Y[0] & X[1] = 1 & 0 = 0
Y[2] = Y[1] | X[2] = 0 | 1 = 1
Finally Y for X is {1, 0, 1} as it end with 1 it will be counted in our answer.
array 7: X = {1, 1, 0}
Y[0] = X[0] = 1
Y[1] = Y[0] & X[1] = 1 & 1 = 1
Y[2] = Y[1] | X[2] = 1 | 0 = 1
Finally Y for X is {1, 1, 1} as it end with 1 it will be counted in our answer.
array 8: X = {1, 1, 1}
Y[0] = X[0] = 1
Y[1] = Y[0] & X[1] = 1 & 1 = 1
Y[2] = Y[1] | X[2] = 1 | 1 = 1
Finally Y for X is {1, 1, 1} as it end with 1 it will be counted in our answer.
Total count of binary arrays that end with 1 are 5Input: arr[] = {‘|’, ‘|’, ‘|’, ‘|’, ‘|’}, K = 0
Output: 63
Naive approach: This problem can be solved based on the following idea:
Basic way to solve this problem is to generate all 2N + 1 combinations of array X and transforming it to Y by recursive brute force.
Time Complexity: O(N * 2N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve to this problem.
- dp[i][j] represents count of binary arrays of size i that ends with binary character j of array Y.
- j keeps track of last element of Y in recursive function.
it can be observed that there are N * 2 states but the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of states. This can be done using recursive structure intact and just store the value in a HashMap and whenever the function is called, return the value store without computing .
Follow the steps below to solve the problem:
- Create a 2D array dp[100001][3] that is initially filled with -1.
- Create a recursive function that takes two parameters i representing the ith index of new arrays X and Y and j representing the last element of array Y.
- Call recursive function for both choosing 1 and choosing 0 as a character for the ith position of X.
- If the answer for a particular state is already computed then just return dp[i][j].
- Check the base case if j is equal to 1 then return 1 else return 0.
- If the answer for a particular state is computed then save it in dp[i][j].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Dp table initialized with - 1int dp[100001][3];// Dp[i][j] represents count of binary strings// of size i with j being its last element of Y// by performing given operations// Recursive function to count ways of forming// binary array Yint recur(int i, int j, char arr[], int N){ // Base case if (i == N + 1) { // Return 1 if at end 1 is formed // in array Y if (j == 1) return 1; else return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j + 1] != -1) return dp[i][j + 1]; // Count of ways for creating binary // array Y of size N + 1 with // Y[N + 1] = 1 int ans = 0; // j is -1 if this is first element // hence Y[0] = X[0]. if (j == -1) { // Calling recursive function // by choosing X[0] = Y[0] = 0 ans += recur(i + 1, 0, arr, N); // Calling recursive function // by choosing X[0] = Y[0] = 1 ans += recur(i + 1, 1, arr, N); } else { // If operation to be performed is AND if (arr[i - 1] == '&') { // Calling recursive function for // X[i] = 1 and Y[i] = j & 1 ans += recur(i + 1, j & 1, arr, N); // Calling recursive function for // X[i] = 0 and Y[i] = j & 0 ans += recur(i + 1, j & 0, arr, N); } // If operation to be performed is OR else { // Calling recursive function for // X[i] = 1 and Y[i] = j | 1 ans += recur(i + 1, j | 1, arr, N); // Calling recursive function for // Y[i] = 0 and Y[i] = j | 0 ans += recur(i + 1, j | 0, arr, N); } } // Save and return dp value return dp[i][j + 1] = ans;}// Counting ways of forming array Y// such that Y[N + 1] == 1void countWaysBinaryArrayY(char arr[], int N){ // Filling dp table with -1 memset(dp, -1, sizeof(dp)); cout << recur(0, -1, arr, N) << endl;}// Driver Codeint main(){ // Input 1 char arr[] = { '&', '|' }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call countWaysBinaryArrayY(arr, N); // Input 2 char arr1[] = { '|', '|', '|', '|', '|' }; int N1 = sizeof(arr1) / sizeof(arr[0]); // Function call countWaysBinaryArrayY(arr1, N1); return 0;} |
Java
// Java code implementation for the above approachimport java.io.*;import java.util.*;class GFG { static int[][] dp = new int[100001][3]; // Recursive function to count ways of forming // binary array Y static int recur(int i, int j, char[] arr, int N) { // Base case if (i == N + 1) { // Return 1 if at end 1 is formed // in array Y if (j == 1) return 1; else return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j + 1] != -1) return dp[i][j + 1]; // Count of ways for creating binary // array Y of size N + 1 with // Y[N + 1] = 1 int ans = 0; // j is -1 if this is first element // hence Y[0] = X[0]. if (j == -1) { // Calling recursive function // by choosing X[0] = Y[0] = 0 ans += recur(i + 1, 0, arr, N); // Calling recursive function // by choosing X[0] = Y[0] = 1 ans += recur(i + 1, 1, arr, N); } else { // If operation to be performed is AND if (arr[i - 1] == '&') { // Calling recursive function for // X[i] = 1 and Y[i] = j & 1 ans += recur(i + 1, j & 1, arr, N); // Calling recursive function for // X[i] = 0 and Y[i] = j & 0 ans += recur(i + 1, j & 0, arr, N); } // If operation to be performed is OR else { // Calling recursive function for // X[i] = 1 and Y[i] = j | 1 ans += recur(i + 1, j | 1, arr, N); // Calling recursive function for // Y[i] = 0 and Y[i] = j | 0 ans += recur(i + 1, j | 0, arr, N); } } // Save and return dp value return dp[i][j + 1] = ans; } // Counting ways of forming array Y // such that Y[N + 1] == 1 static void CountWaysBinaryArrayY(char[] arr, int N) { // Filling dp table with -1 for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[i].length; j++) { dp[i][j] = -1; } } System.out.println(recur(0, -1, arr, N)); } public static void main(String[] args) { // Input 1 char[] arr = { '&', '|' }; int N = arr.length; // Function Call CountWaysBinaryArrayY(arr, N); // Input 2 char[] arr1 = { '|', '|', '|', '|', '|' }; int N1 = arr1.length; // Function call CountWaysBinaryArrayY(arr1, N1); }}// This code is contributed by lokesh. |
Python3
# python3 code to implement the approach# Dp table initialized with - 1dp = [[-1 for _ in range(3)] for _ in range(100001)]# Dp[i][j] represents count of binary strings# of size i with j being its last element of Y# by performing given operations# Recursive function to count ways of forming# binary array Ydef recur(i, j, arr, N): global dp # Base case if (i == N + 1): # Return 1 if at end 1 is formed # in array Y if (j == 1): return 1 else: return 0 # If answer for current state is already # calculated then just return dp[i][j] if (dp[i][j + 1] != -1): return dp[i][j + 1] # Count of ways for creating binary # array Y of size N + 1 with # Y[N + 1] = 1 ans = 0 # j is -1 if this is first element # hence Y[0] = X[0]. if (j == -1): # Calling recursive function # by choosing X[0] = Y[0] = 0 ans += recur(i + 1, 0, arr, N) # Calling recursive function # by choosing X[0] = Y[0] = 1 ans += recur(i + 1, 1, arr, N) else: # If operation to be performed is AND if (arr[i - 1] == '&'): # Calling recursive function for # X[i] = 1 and Y[i] = j & 1 ans += recur(i + 1, j & 1, arr, N) # Calling recursive function for # X[i] = 0 and Y[i] = j & 0 ans += recur(i + 1, j & 0, arr, N) # If operation to be performed is OR else: # Calling recursive function for # X[i] = 1 and Y[i] = j | 1 ans += recur(i + 1, j | 1, arr, N) # Calling recursive function for # Y[i] = 0 and Y[i] = j | 0 ans += recur(i + 1, j | 0, arr, N) # Save and return dp value dp[i][j + 1] = ans return ans# Counting ways of forming array Y# such that Y[N + 1] == 1def countWaysBinaryArrayY(arr, N): # Filling dp table with -1 global dp dp = [[-1 for _ in range(3)] for _ in range(100001)] print(recur(0, -1, arr, N))# Driver Codeif __name__ == "__main__": # Input 1 arr = ['&', '|'] N = len(arr) # Function Call countWaysBinaryArrayY(arr, N) # Input 2 arr1 = ['|', '|', '|', '|', '|'] N1 = len(arr1) # Function call countWaysBinaryArrayY(arr1, N1) # This code is contributed by rakeshsahni |
C#
//c# code implementationusing System;public class GFG { static int[, ] dp = new int[100001, 3]; // Recursive function to count ways of forming // binary array Y static int recur(int i, int j, char[] arr, int N) { // Base case if (i == N + 1) { // Return 1 if at end 1 is formed // in array Y if (j == 1) return 1; else return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i, j + 1] != -1) return dp[i, j + 1]; // Count of ways for creating binary // array Y of size N + 1 with // Y[N + 1] = 1 int ans = 0; // j is -1 if this is first element // hence Y[0] = X[0]. if (j == -1) { // Calling recursive function // by choosing X[0] = Y[0] = 0 ans += recur(i + 1, 0, arr, N); // Calling recursive function // by choosing X[0] = Y[0] = 1 ans += recur(i + 1, 1, arr, N); } else { // If operation to be performed is AND if (arr[i - 1] == '&') { // Calling recursive function for // X[i] = 1 and Y[i] = j & 1 ans += recur(i + 1, j & 1, arr, N); // Calling recursive function for // X[i] = 0 and Y[i] = j & 0 ans += recur(i + 1, j & 0, arr, N); } // If operation to be performed is OR else { // Calling recursive function for // X[i] = 1 and Y[i] = j | 1 ans += recur(i + 1, j | 1, arr, N); // Calling recursive function for // Y[i] = 0 and Y[i] = j | 0 ans += recur(i + 1, j | 0, arr, N); } } // Save and return dp value return dp[i, j + 1] = ans; } // Counting ways of forming array Y // such that Y[N + 1] == 1 static void CountWaysBinaryArrayY(char[] arr, int N) { // Filling dp table with -1 for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) { dp[i, j] = -1; } } Console.WriteLine(recur(0, -1, arr, N)); } static void Main(string[] args) { // Input 1 //char[] arr = { '& char[] arr = { '&', '|' }; int N = arr.Length; // Function Call CountWaysBinaryArrayY(arr, N); // Input 2 char[] arr1 = { '|', '|', '|', '|', '|' }; int N1 = arr1.Length; // Function call CountWaysBinaryArrayY(arr1, N1); }}// code by ksam24000 |
Javascript
// Javascript code to implement the approach// Dp table initialized with - 1let dp = new Array(100001);for(let i=0; i<100001; i++) dp[i]=new Array(3);// Dp[i][j] represents count of binary strings// of size i with j being its last element of Y// by performing given operations// Recursive function to count ways of forming// binary array Yfunction recur( i, j, arr, N){ // Base case if (i == N + 1) { // Return 1 if at end 1 is formed // in array Y if (j == 1) return 1; else return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j + 1] != -1) return dp[i][j + 1]; // Count of ways for creating binary // array Y of size N + 1 with // Y[N + 1] = 1 let ans = 0; // j is -1 if this is first element // hence Y[0] = X[0]. if (j == -1) { // Calling recursive function // by choosing X[0] = Y[0] = 0 ans += recur(i + 1, 0, arr, N); // Calling recursive function // by choosing X[0] = Y[0] = 1 ans += recur(i + 1, 1, arr, N); } else { // If operation to be performed is AND if (arr[i - 1] == '&') { // Calling recursive function for // X[i] = 1 and Y[i] = j & 1 ans += recur(i + 1, j & 1, arr, N); // Calling recursive function for // X[i] = 0 and Y[i] = j & 0 ans += recur(i + 1, j & 0, arr, N); } // If operation to be performed is OR else { // Calling recursive function for // X[i] = 1 and Y[i] = j | 1 ans += recur(i + 1, j | 1, arr, N); // Calling recursive function for // Y[i] = 0 and Y[i] = j | 0 ans += recur(i + 1, j | 0, arr, N); } } // Save and return dp value return dp[i][j + 1] = ans;}// Counting ways of forming array Y// such that Y[N + 1] == 1function countWaysBinaryArrayY( arr, N){ // Filling dp table with -1 for(let i=0; i<100001; i++) for(let j=0; j<3; j++) dp[i][j]=-1; document.write(recur(0, -1, arr, N))}// Driver Code // Input 1 let arr = [ '&', '|' ]; let N = arr.length; // Function Call countWaysBinaryArrayY(arr, N); document.write("<br>"); // Input 2 let arr1 = ['|', '|', '|', '|', '|' ]; let N1 = arr1.length; // Function call countWaysBinaryArrayY(arr1, N1); |
5 63
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles :
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
