Toggle Bitwise Expression - Google Top Interview Questions
Problem Statement :
You are given a string s representing a bitwise expression with the following characters: "0", "1", "&", "|", "(", and ")".
In one operation, you can:
Toggle "0" to "1"
Toggle "1" to "0"
Change "&" to "|"
Change "|" to "&"
Return the minimum number of operations required to toggle the value of the expression.
Note: the precedence of the operators don't matter, since they'll be wrapped in brackets when
necessary. For example, "1&0" and "1&(0&1)" are possible inputs but "1&0&1" will not occur.
Constraints
1 ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = "0&(0&(0&0))"
Output
2
Explanation
The input expression evaluates to 0. To toggle it to 1, we can change the expression to "1|(0&(0&0))".
Example 2
Input
s = "(1|1)|(1|1)"
Output
3
Explanation
The input expression evaluates to 1. To toggle it to 0, we can change the expression to "(0&1)&(1|1)".
Example 3
Input
s = "0&0"
Output
2
Solution :
Solution in C++ :
int pairing[1000005];
unordered_map<long long, int> dp;
int force(string& s, int start, int end, int want) {
if (start == end) {
if (s[start] - '0' == want) return 0;
return 1;
}
long long key = (1000000LL * start) + (10 * end) + want;
if (dp.count(key)) return dp[key];
int ret = 1e9;
int lhs[2];
int rhs[2];
if (s[start] == '(' && s[end] == ')' && pairing[start] == end) {
return dp[key] = force(s, start + 1, end - 1, want);
}
if (s[start] == '(') {
int end = pairing[start];
lhs[0] = force(s, start + 1, end - 1, 0);
lhs[1] = force(s, start + 1, end - 1, 1);
start = end + 1;
} else {
int have = s[start++] - '0';
if (have == 0) {
lhs[0] = 0;
lhs[1] = 1;
} else {
lhs[0] = 1;
lhs[1] = 0;
}
}
char op = s[start++];
rhs[0] = force(s, start, end, 0);
rhs[1] = force(s, start, end, 1);
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
if ((a | b) == want) {
int cost = lhs[a] + rhs[b];
if (op == '&') cost++;
ret = min(ret, cost);
}
if ((a & b) == want) {
int cost = lhs[a] + rhs[b];
if (op == '|') cost++;
ret = min(ret, cost);
}
}
}
dp[key] = ret;
return ret;
}
int eval(string& s, int start, int end) {
assert(start <= end);
if (start == end) {
assert(s[start] == '0' || s[start] == '1');
return s[start] - '0';
}
if (s[start] == '(' && s[end] == ')' && pairing[start] == end) {
return eval(s, start + 1, end - 1);
}
int lhs;
if (s[start] == '(') {
int end = pairing[start];
lhs = eval(s, start + 1, end - 1);
start = end + 1;
} else {
lhs = s[start++] - '0';
}
char op = s[start++];
int rhs = eval(s, start, end);
if (op == '&') {
if (lhs == 0 || rhs == 0) return 0;
return 1;
}
if (op == '|') {
if (lhs == 1 || rhs == 1) return 1;
return 0;
}
assert(false);
}
int solve(string s) {
stack<int> paren;
for (int i = 0; i < s.size(); i++) pairing[i] = -1;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
paren.push(i);
} else if (s[i] == ')') {
int lhs = paren.top();
paren.pop();
pairing[lhs] = i;
pairing[i] = lhs;
}
}
int want = eval(s, 0, s.size() - 1);
dp.clear();
return force(s, 0, s.size() - 1, want ^ 1);
}
Solution in Java :
import java.util.*;
class Solution {
private static final class Tree {
private char op = ' ';
private int val = -1;
private Tree left, right;
public Tree(char op) {
this.op = op;
}
public Tree(int val) {
this.val = val;
}
}
private int idx = -1;
public int solve(String s) {
idx = 0;
Stack<Tree> stack = new Stack<>();
build(s, stack);
final Tree ROOT = stack.pop();
int[] res = dfs(ROOT);
return Math.abs(res[0] - res[1]);
}
private int[] dfs(Tree node) {
if (node.val != -1) {
return new int[] {node.val, 1 ^ node.val};
}
int[] left = dfs(node.left);
int[] right = dfs(node.right);
if (node.op == '&') {
int zero = Math.min(left[0], right[0]);
int one = Math.min(left[1] + right[1], 1 + Math.min(left[1], right[1]));
return new int[] {zero, one};
} else {
int zero = Math.min(left[0] + right[0], 1 + Math.min(left[0], right[0]));
int one = Math.min(left[1], right[1]);
return new int[] {zero, one};
}
}
private void build(String s, Stack<Tree> stack) {
if (idx == s.length())
return;
final char ch = s.charAt(idx);
if (ch == '0' || ch == '1') {
idx++;
final Tree node = new Tree(ch - '0');
if (stack.isEmpty())
stack.push(node);
else
stack.peek().right = node;
} else if (ch == '(') {
idx++;
Stack<Tree> tmp = new Stack<>();
build(s, tmp);
if (stack.isEmpty())
stack.push(tmp.pop());
else
stack.peek().right = tmp.pop();
idx++;
} else if (ch == ')') {
return;
} else {
final Tree node = new Tree(ch);
node.left = stack.pop();
stack.push(node);
idx++;
}
build(s, stack);
}
}
Solution in Python :
class Solution:
def solve(self, st):
if len(st) == 1:
return 1
st = "(" + st + ")"
s = []
for x in st:
if x == ")":
# az = min number of edits get to zero on the "a" side
# ao = min number of edits to get to one on the "a" side
az, ao = s.pop()
op = s.pop()
# bz = min number of edits get to zero on the "a" side
# bo = min number of edits to get to one on the "a" side
bz, bo = s.pop()
nz, no = None, None
if op == "|":
# These are just the "standard" way without edits, the new way to get to zero is if both the left and the right are zeroes
nz = az + bz
# We take the cheapest way to get to one by enumerating all the possibilities of a|b ->
# the cost of (a = 0, b = 1), (a = 1, b = 1), (a = 1, b = 0)
no = min(az + bo, ao + bo, ao + bz)
# These are the cost of changing either the left or the right
# another way to get to zero is starting from (a = 0, b = 1), and changing b = 0, with a cost of bo, or (a = 1, b = 0), and changing a = 0, with a cost of ao
nz = min(nz, az + bo + bz, ao + bz + az)
# if a = 0, b = 0, we either change b to 1 (with the cost of bo) or we change a to 1 (with cost of ao)
no = min(no, az + bz + bo, az + bz + ao)
# we can also change the sign - we can get to zero if we change to "and", and it will cost "1" to change the operator
nz = min(nz, min(az + bz, az + bo, ao + bz) + 1)
# we can get to one if we already have ones and change the signs to "and". (Note, this is never going to be true as 1|1 == 1&1, but here for symmetry)
no = min(no, ao + bo + 1)
else:
# Same logic, but for "and"
nz = min(az + bz, az + bo, ao + bz)
no = ao + bo
nz = min(nz, ao + bo + az, ao + bo + bz)
no = min(no, az + bo + ao, ao + bz + bo)
nz = min(nz, az + bz + 1)
no = min(no, min(az + bo, ao + bo, ao + bz) + 1)
s.append((nz, no))
elif x in "01":
if int(x) == 0:
s.append((0, 1))
else:
s.append((1, 0))
elif x not in "(":
s.append(x)
return max(s[0])
View More Similar Problems
2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →