Given a boolean expression as a string expression consisting only of the characters '0' (false), '1' (true), '&' (AND), '|' (OR), '(', and ')', you are to determine the minimum number of changes needed to flip the final value of the expression. You may change any '0' to '1' or vice versa, or change any '&' to '|' or vice versa. Each change costs 1.
The expression is always valid and fully parenthesized. Your task is to find the minimum cost required to change the final evaluated result of the expression (i.e., if the expression currently evaluates to 1, find the minimum cost to make it evaluate to 0, and vice versa).
At first glance, one might consider brute-forcing all possible single-character changes and evaluating the result each time, but this quickly becomes infeasible for large expressions. Instead, we must recognize that the problem can be approached recursively: every sub-expression can be evaluated for the minimum cost to make it 0 or 1.
By thinking recursively, we can break down the expression into its components, calculate the minimum cost to achieve both possible outcomes at each node, and then combine these results intelligently. This is similar to evaluating an expression tree, where each node represents an operator and each leaf a value.
The key insight is to propagate the minimum cost for both 0 and 1 up the tree, considering both flipping values and operators at each step. This avoids redundant work and ensures efficiency.
We solve the problem by parsing the expression and, for every subexpression, computing two values:
0.1.'0' or '1'), push a tuple representing its costs (cost_to_0, cost_to_1).'&':
1: both sides must be 1 (cost is sum of both cost_to_1).0: at least one side is 0 (cost is min of left cost_to_0 + right cost_to_1, etc.).'|'.We use a stack-based approach to avoid explicit recursion, and memoize results for efficiency.
Consider the expression "1&(0|1)":
0|1:
1: either side is 1. So, cost = min(left cost_to_1 + right cost_to_1, etc.).0: both sides must be 0.1&(...):
1: both must be 1.0: at least one is 0.1, and we want 0. The minimum cost is 1, since flipping the '&' to '|' will suffice.class Solution:
def minOperationsToFlip(self, expression: str) -> int:
stack = []
for c in expression:
if c == ' ':
continue
elif c == '(':
stack.append(c)
elif c in '01':
# (cost to make 0, cost to make 1, current value)
stack.append((int(c) ^ 1, 0 if c == '1' else 1, int(c)))
elif c in '&|':
stack.append(c)
elif c == ')':
right = stack.pop()
op = stack.pop()
left = stack.pop()
stack.pop() # remove '('
# left and right: (cost_to_0, cost_to_1, value)
l0, l1, lv = left
r0, r1, rv = right
# As is
if op == '&':
v = lv & rv
cost0 = min(
l0 + r0,
l0 + r1,
l1 + r0
)
cost1 = l1 + r1
else:
v = lv | rv
cost1 = min(
l1 + r1,
l0 + r1,
l1 + r0
)
cost0 = l0 + r0
# If flip operator
if op == '&':
# as if it was '|'
flip_cost1 = min(
l1 + r1,
l0 + r1,
l1 + r0
) + 1
flip_cost0 = l0 + r0 + 1
else:
# as if it was '&'
flip_cost0 = min(
l0 + r0,
l0 + r1,
l1 + r0
) + 1
flip_cost1 = l1 + r1 + 1
min0 = min(cost0, flip_cost0)
min1 = min(cost1, flip_cost1)
stack.append((min0, min1, v))
# At the end, only one tuple remains
cost0, cost1, val = stack[0]
return cost0 if val == 1 else cost1
class Solution {
public:
int minOperationsToFlip(string expression) {
stack<any> st;
for (char c : expression) {
if (c == ' ') continue;
if (c == '(') {
st.push(c);
} else if (c == '0' || c == '1') {
int v = c - '0';
st.push(tuple<int,int,int>(v == 0 ? 0 : 1, v == 1 ? 0 : 1, v));
} else if (c == '&' || c == '|') {
st.push(c);
} else if (c == ')') {
auto right = any_cast<tuple<int,int,int>>(st.top()); st.pop();
char op = any_cast<char>(st.top()); st.pop();
auto left = any_cast<tuple<int,int,int>>(st.top()); st.pop();
st.pop(); // '('
int l0, l1, lv, r0, r1, rv;
tie(l0, l1, lv) = left;
tie(r0, r1, rv) = right;
int cost0, cost1, flip_cost0, flip_cost1, v;
if (op == '&') {
v = lv & rv;
cost0 = min({l0 + r0, l0 + r1, l1 + r0});
cost1 = l1 + r1;
flip_cost1 = min({l1 + r1, l0 + r1, l1 + r0}) + 1;
flip_cost0 = l0 + r0 + 1;
} else {
v = lv | rv;
cost1 = min({l1 + r1, l0 + r1, l1 + r0});
cost0 = l0 + r0;
flip_cost0 = min({l0 + r0, l0 + r1, l1 + r0}) + 1;
flip_cost1 = l1 + r1 + 1;
}
int min0 = min(cost0, flip_cost0);
int min1 = min(cost1, flip_cost1);
st.push(tuple<int,int,int>(min0, min1, v));
}
}
auto res = any_cast<tuple<int,int,int>>(st.top());
int cost0, cost1, val;
tie(cost0, cost1, val) = res;
return val == 1 ? cost0 : cost1;
}
};
import java.util.*;
class Solution {
public int minOperationsToFlip(String expression) {
Deque<Object> stack = new ArrayDeque<>();
for (char c : expression.toCharArray()) {
if (c == ' ') continue;
if (c == '(') {
stack.push(c);
} else if (c == '0' || c == '1') {
int v = c - '0';
stack.push(new int[]{v == 0 ? 0 : 1, v == 1 ? 0 : 1, v});
} else if (c == '&' || c == '|') {
stack.push(c);
} else if (c == ')') {
int[] right = (int[]) stack.pop();
char op = (char) stack.pop();
int[] left = (int[]) stack.pop();
stack.pop(); // '('
int l0 = left[0], l1 = left[1], lv = left[2];
int r0 = right[0], r1 = right[1], rv = right[2];
int cost0, cost1, flip_cost0, flip_cost1, v;
if (op == '&') {
v = lv & rv;
cost0 = Math.min(Math.min(l0 + r0, l0 + r1), l1 + r0);
cost1 = l1 + r1;
flip_cost1 = Math.min(Math.min(l1 + r1, l0 + r1), l1 + r0) + 1;
flip_cost0 = l0 + r0 + 1;
} else {
v = lv | rv;
cost1 = Math.min(Math.min(l1 + r1, l0 + r1), l1 + r0);
cost0 = l0 + r0;
flip_cost0 = Math.min(Math.min(l0 + r0, l0 + r1), l1 + r0) + 1;
flip_cost1 = l1 + r1 + 1;
}
int min0 = Math.min(cost0, flip_cost0);
int min1 = Math.min(cost1, flip_cost1);
stack.push(new int[]{min0, min1, v});
}
}
int[] res = (int[]) stack.pop();
int cost0 = res[0], cost1 = res[1], val = res[2];
return val == 1 ? cost0 : cost1;
}
}
var minOperationsToFlip = function(expression) {
let stack = [];
for (let c of expression) {
if (c === ' ') continue;
if (c === '(') {
stack.push(c);
} else if (c === '0' || c === '1') {
let v = Number(c);
stack.push([v === 0 ? 0 : 1, v === 1 ? 0 : 1, v]);
} else if (c === '&' || c === '|') {
stack.push(c);
} else if (c === ')') {
let right = stack.pop();
let op = stack.pop();
let left = stack.pop();
stack.pop(); // '('
let [l0, l1, lv] = left;
let [r0, r1, rv] = right;
let cost0, cost1, flip_cost0, flip_cost1, v;
if (op === '&') {
v = lv & rv;
cost0 = Math.min(l0 + r0, l0 + r1, l1 + r0);
cost1 = l1 + r1;
flip_cost1 = Math.min(l1 + r1, l0 + r1, l1 + r0) + 1;
flip_cost0 = l0 + r0 + 1;
} else {
v = lv | rv;
cost1 = Math.min(l1 + r1, l0 + r1, l1 + r0);
cost0 = l0 + r0;
flip_cost0 = Math.min(l0 + r0, l0 + r1, l1 + r0) + 1;
flip_cost1 = l1 + r1 + 1;
}
let min0 = Math.min(cost0, flip_cost0);
let min1 = Math.min(cost1, flip_cost1);
stack.push([min0, min1, v]);
}
}
let [cost0, cost1, val] = stack[0];
return val === 1 ? cost0 : cost1;
};
Brute-force approach: Trying all possible single-character changes and evaluating the expression each time would result in exponential time complexity, as every character can be flipped, and each flip can affect the overall outcome. This is not feasible for large expressions.
Optimized approach (as above): Each character in the expression is processed a constant number of times, and for each subexpression, we compute and store two values (cost to 0 and cost to 1). Thus:
This problem is elegantly solved by treating the expression as a tree and recursively (or iteratively with a stack) computing the minimum cost to flip each subexpression. By considering both flipping values and operators at each step, and propagating these costs upward, we avoid brute-force enumeration and achieve a linear-time solution. The key insight is to always keep track of both possible outcomes for each subexpression, enabling an optimal solution with minimal work.