Scale Engineer

Minimum Cost to Change the Final Value of Expression

Hard
#1730Time: O(N^2), where N is the length of the expression. For each subproblem of length `k`, we scan it in O(k) time to find the split point. The sum of work across all subproblems leads to an O(N^2) complexity in the worst case (e.g., for expressions like `1&1&1...&1`).Space: O(N^2), where N is the length of the expression. The memoization can store up to O(N^2) subproblems, and the sum of the lengths of these subproblem strings can also be O(N^2). The recursion depth can go up to O(N).
Patterns
MathDynamic Programming
Data structures
StringStack

Prompt

You are given a valid boolean expression as a string expression consisting of the characters '1','0','&' (bitwise AND operator),'|' (bitwise OR operator),'(', and ')'.

  • For example, "()1|1" and "(1)&()" are not valid while "1", "(((1))|(0))", and "1|(0&(1))" are valid expressions.

Return the minimum cost to change the final value of the expression.

  • For example, if expression = "1|1|(0&0)&1", its value is 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1. We want to apply operations so that the new expression evaluates to 0.

The cost of changing the final value of an expression is the number of operations performed on the expression. The types of operations are described as follows:

  • Turn a '1' into a '0'.
  • Turn a '0' into a '1'.
  • Turn a '&' into a '|'.
  • Turn a '|' into a '&'.

Note: '&' does not take precedence over '|' in the order of calculation. Evaluate parentheses first, then in left-to-right order.

 

Example 1:

Input: expression = "1&(0|1)"
Output: 1
Explanation: We can turn "1&(0|1)" into "1&(0&1)" by changing the '|' to a '&' using 1 operation.
The new expression evaluates to 0.

Example 2:

Input: expression = "(0&0)&(0&0&0)"
Output: 3
Explanation: We can turn "(0&0)&(0&0&0)" into "(0|1)|(0&0&0)" using 3 operations.
The new expression evaluates to 1.

Example 3:

Input: expression = "(0|(1|0&1))"
Output: 1
Explanation: We can turn "(0|(1|0&1))" into "(0|(0|0&1))" using 1 operation.
The new expression evaluates to 0.

 

Constraints:

  • 1 <= expression.length <= 105
  • expression only contains '1','0','&','|','(', and ')'
  • All parentheses are properly matched.
  • There will be no empty parentheses (i.e: "()" is not a substring of expression).

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses recursion to solve the problem, mirroring the recursive nature of the expression itself. We define a function that takes a subexpression and returns the minimum cost to make it evaluate to 0 and the minimum cost to make it evaluate to 1. To avoid recomputing the same subproblem, we use memoization.

Algorithm

  • The core idea is to use recursion to break down the expression into smaller subproblems. We define a function, say solve(subExpression), that computes the minimum costs.
  • The state for our recursion/dynamic programming will be a pair of values: {cost_to_evaluate_to_0, cost_to_evaluate_to_1}.
  • Base Cases:
    • If subExpression is '0', the cost to make it 0 is 0, and to make it 1 is 1. So we return {0, 1}.
    • If subExpression is '1', the cost to make it 0 is 1, and to make it 1 is 0. So we return {1, 0}.
  • Recursive Step:
    • For a complex subExpression, we first need to find its main operator. Due to the left-to-right evaluation rule (with parentheses taking precedence), the main operator is the last & or | that is not enclosed in parentheses.
    • We can find this by scanning the subexpression from right to left, keeping track of the parenthesis nesting level. The first operator found at level 0 is our split point.
    • If no such operator is found, the expression must be fully enclosed in parentheses (e.g., (1&0)). In this case, we strip the outer parentheses and recurse on the inner part.
    • Once we split the expression E into E1 op E2, we recursively call solve(E1) and solve(E2) to get their respective cost pairs, say {c1_0, c1_1} and {c2_0, c2_1}.
    • We then combine these results using predefined formulas to calculate the costs for E.
  • Combining Results: For an expression E1 op E2:
    • If op is &:
      • cost(E, 0) = min(min(c1_0, c2_0), 1 + c1_0 + c2_0)
      • cost(E, 1) = min(c1_1 + c2_1, 1 + min(c1_1, c2_1))
    • If op is |:
      • cost(E, 0) = min(c1_0 + c2_0, 1 + min(c1_0, c2_0))
      • cost(E, 1) = min(min(c1_1, c2_1), 1 + c1_1 + c2_1)
  • Memoization: To avoid recomputing results for the same subexpressions, we use a hash map or a 2D array to store the results of solve(subExpression).

Walkthrough

We can define a recursive function, for instance solve(expression_string), which computes a pair of values: the minimum cost to make the expression evaluate to 0, and the minimum cost to make it evaluate to 1. The base cases for the recursion are single-digit strings '0' and '1'. For any other expression, we find the main operator (the last one evaluated according to the rules) and split the expression into two operands. We then make recursive calls on these operands. The results from the recursive calls are combined based on the operator. For example, to make E1 & E2 evaluate to 1, we must make both E1 and E2 evaluate to 1, so the cost is the sum of their costs to become 1. We also consider the option of changing the operator itself (e.g., & to |) for an additional cost of 1. Since the same subexpression can appear multiple times, we use memoization to store and reuse the results, effectively turning the recursion into dynamic programming.

class Solution {    private Map<String, int[]> memo;     public int minOperationsToFlip(String expression) {        memo = new HashMap<>();        int[] costs = solve(expression);        // The cost to achieve the original value is 0.        // The cost to flip is the other value in the pair.        // So, the answer is the maximum of the two costs.        return Math.max(costs[0], costs[1]);    }     private int[] solve(String expr) {        if (memo.containsKey(expr)) {            return memo.get(expr);        }        if (expr.equals("0")) {            return new int[]{0, 1}; // {cost_for_0, cost_for_1}        }        if (expr.equals("1")) {            return new int[]{1, 0};        }         int balance = 0;        int splitIndex = -1;        // Find the last operator at parenthesis level 0        for (int i = expr.length() - 1; i >= 0; i--) {            char c = expr.charAt(i);            if (c == ')') balance++;            else if (c == '(') balance--;            else if (balance == 0 && (c == '&' || c == '|')) {                splitIndex = i;                break;            }        }         int[] result;        if (splitIndex == -1) { // Expression is wrapped in parentheses            result = solve(expr.substring(1, expr.length() - 1));        } else {            char op = expr.charAt(splitIndex);            String leftExpr = expr.substring(0, splitIndex);            String rightExpr = expr.substring(splitIndex + 1);             int[] leftCosts = solve(leftExpr);            int[] rightCosts = solve(rightExpr);            int c1_0 = leftCosts[0], c1_1 = leftCosts[1];            int c2_0 = rightCosts[0], c2_1 = rightCosts[1];             result = new int[2];            if (op == '&') {                result[0] = Math.min(Math.min(c1_0, c2_0), 1 + c1_0 + c2_0);                result[1] = Math.min(c1_1 + c2_1, 1 + Math.min(c1_1, c2_1));            } else { // op == '|'                result[0] = Math.min(c1_0 + c2_0, 1 + Math.min(c1_0, c2_0));                result[1] = Math.min(Math.min(c1_1, c2_1), 1 + c1_1 + c2_1);            }        }         memo.put(expr, result);        return result;    }}

Complexity

Time

O(N^2), where N is the length of the expression. For each subproblem of length `k`, we scan it in O(k) time to find the split point. The sum of work across all subproblems leads to an O(N^2) complexity in the worst case (e.g., for expressions like `1&1&1...&1`).

Space

O(N^2), where N is the length of the expression. The memoization can store up to O(N^2) subproblems, and the sum of the lengths of these subproblem strings can also be O(N^2). The recursion depth can go up to O(N).

Trade-offs

Pros

  • The recursive structure of the solution closely matches the recursive structure of the problem, making it conceptually straightforward.

Cons

  • The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a Time Limit Exceeded error.

  • The space complexity of O(N^2) can be very high.

  • Repeatedly creating substrings is inefficient in Java.

Solutions

class Solution {public  int minOperationsToFlip(String expression) {    Deque<Integer> numStack = new LinkedList<Integer>();    Deque<Integer> opStack = new LinkedList<Integer>();    Deque<Character> signStack = new LinkedList<Character>();    int length = expression.length();    for (int i = 0; i < length; i++) {      char c = expression.charAt(i);      if (Character.isDigit(c)) {        numStack.push((int)(c - '0'));        opStack.push(1);      } else if (c == ')')        signStack.pop();      else {        signStack.push(c);        continue;      }      if (numStack.size() > 1 && signStack.peek() != '(') {        int num2 = numStack.pop();        int num1 = numStack.pop();        int op2 = opStack.pop();        int op1 = opStack.pop();        char sign = signStack.pop();        int[] ops = minOp(num1, num2, op1, op2, sign);        numStack.push(ops[0]);        opStack.push(ops[1]);      }    }    return opStack.pop();  }public  int[] minOp(int num1, int num2, int op1, int op2, char sign) {    if (sign == '&') {      if (num1 == 1 && num2 == 1)        return new int[]{1, Math.min(op1, op2)};      else if (num1 == 0 && num2 == 0)        return new int[]{0, Math.min(op1, op2) + 1};      else        return new int[]{0, 1};    } else {      if (num1 == 0 && num2 == 0)        return new int[]{0, Math.min(op1, op2)};      else if (num1 == 1 && num2 == 1)        return new int[]{1, Math.min(op1, op2) + 1};      else        return new int[]{1, 1};    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem