Count ways of creating Binary Array ending with 1 using Binary operators – GeeksforGeeks

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 5

Input: 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 2^{N + 1} combinations of array X and transforming it to Y by recursive brute force.

Time Complexity: O(N * 2^N)
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 i^th 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 i^th 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:

Time Complexity: O(N)
Auxiliary Space: O(N)

Related Articles :