Skip to content

1896. Minimum Cost to Change the Final Value of Expression

SourceBiweekly Contest 54 Q4DifficultyHardRating2531

Description

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).

Solutions

Solution 1

Thinking

A valid boolean expression uses \(0/1\), \(\&\), \(|\), and parentheses. One edit flips a digit or an operator. The expression can have length \(10^5\), so reevaluating every edit is impossible.

Each subexpression only needs its current value and the cost of flipping it. A leaf costs \(1\) to flip. When two sides are joined by \(\&\) or \(|\), the flip cost follows from changing the operator, one child, or both. A stack parses parentheses and operators and merges these pairs from the bottom up.

Represent each subexpression by \((\textit{val},\textit{cost})\): its current boolean value and the minimum edits that flip it. A digit costs \(1\) to flip.

\(\&\) and \(|\) have the same precedence and associate left to right; parentheses bind tighter. Two stacks store subexpressions and operators. An operator reduces any pending operator of the same precedence, and a closing parenthesis reduces until the matching opening parenthesis.

Let the two sides be \((v_1,c_1)\) and \((v_2,c_2)\).

  • For \(\&\) with both sides \(1\), the value is \(1\) and the flip cost is \(\min(c_1,c_2)\).
  • With both sides \(0\), the value is \(0\). Flipping both operands costs \(c_1+c_2\); changing \(\&\) to \(|\) and flipping one operand costs \(1+\min(c_1,c_2)\).
  • With exactly one \(0\), the value is \(0\). Flip that \(0\), or change \(\&\) to \(|\), and take the cheaper cost.
  • The three cases for \(|\) are dual to the cases above.

After the expression is reduced, the top \(\textit{cost}\) is the answer.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the expression.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        def merge(a, b, op):
            v1, c1 = a
            v2, c2 = b
            if op == '&':
                val = v1 & v2
                if v1 == 1 and v2 == 1:
                    cost = min(c1, c2)
                elif v1 == 0 and v2 == 0:
                    cost = min(c1 + c2, 1 + min(c1, c2))
                else:
                    cost = min(c1 if v1 == 0 else c2, 1)
            else:
                val = v1 | v2
                if v1 == 0 and v2 == 0:
                    cost = min(c1, c2)
                elif v1 == 1 and v2 == 1:
                    cost = min(c1 + c2, 1 + min(c1, c2))
                else:
                    cost = min(c1 if v1 == 1 else c2, 1)
            return val, cost

        nums = []
        ops = []

        def apply():
            b = nums.pop()
            a = nums.pop()
            nums.append(merge(a, b, ops.pop()))

        for c in expression:
            if c == '(':
                ops.append(c)
            elif c in '01':
                nums.append((int(c), 1))
            elif c in '&|':
                while ops and ops[-1] in '&|':
                    apply()
                ops.append(c)
            else:
                while ops[-1] != '(':
                    apply()
                ops.pop()
        while ops:
            apply()
        return nums[-1][1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public int minOperationsToFlip(String expression) {
        int n = expression.length();
        int[] val = new int[n];
        int[] cost = new int[n];
        int top = 0;
        char[] ops = new char[n];
        int otop = 0;
        for (int i = 0; i < n; ++i) {
            char c = expression.charAt(i);
            if (c == '(') {
                ops[otop++] = c;
            } else if (c == '0' || c == '1') {
                val[top] = c - '0';
                cost[top++] = 1;
            } else if (c == '&' || c == '|') {
                while (otop > 0 && (ops[otop - 1] == '&' || ops[otop - 1] == '|')) {
                    merge(val, cost, top, ops[--otop]);
                    --top;
                }
                ops[otop++] = c;
            } else {
                while (ops[otop - 1] != '(') {
                    merge(val, cost, top, ops[--otop]);
                    --top;
                }
                --otop;
            }
        }
        while (otop > 0) {
            merge(val, cost, top, ops[--otop]);
            --top;
        }
        return cost[0];
    }

    private void merge(int[] val, int[] cost, int top, char op) {
        int v1 = val[top - 2], c1 = cost[top - 2];
        int v2 = val[top - 1], c2 = cost[top - 1];
        if (op == '&') {
            val[top - 2] = v1 & v2;
            if (v1 == 1 && v2 == 1) {
                cost[top - 2] = Math.min(c1, c2);
            } else if (v1 == 0 && v2 == 0) {
                cost[top - 2] = Math.min(c1 + c2, 1 + Math.min(c1, c2));
            } else {
                cost[top - 2] = Math.min(v1 == 0 ? c1 : c2, 1);
            }
        } else {
            val[top - 2] = v1 | v2;
            if (v1 == 0 && v2 == 0) {
                cost[top - 2] = Math.min(c1, c2);
            } else if (v1 == 1 && v2 == 1) {
                cost[top - 2] = Math.min(c1 + c2, 1 + Math.min(c1, c2));
            } else {
                cost[top - 2] = Math.min(v1 == 1 ? c1 : c2, 1);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    int minOperationsToFlip(string expression) {
        vector<pair<int, int>> nums;
        vector<char> ops;
        auto merge = [&](char op) {
            auto b = nums.back();
            nums.pop_back();
            auto a = nums.back();
            nums.pop_back();
            int v1 = a.first, c1 = a.second, v2 = b.first, c2 = b.second;
            int val, cost;
            if (op == '&') {
                val = v1 & v2;
                if (v1 == 1 && v2 == 1) {
                    cost = min(c1, c2);
                } else if (v1 == 0 && v2 == 0) {
                    cost = min(c1 + c2, 1 + min(c1, c2));
                } else {
                    cost = min(v1 == 0 ? c1 : c2, 1);
                }
            } else {
                val = v1 | v2;
                if (v1 == 0 && v2 == 0) {
                    cost = min(c1, c2);
                } else if (v1 == 1 && v2 == 1) {
                    cost = min(c1 + c2, 1 + min(c1, c2));
                } else {
                    cost = min(v1 == 1 ? c1 : c2, 1);
                }
            }
            nums.emplace_back(val, cost);
        };
        for (char c : expression) {
            if (c == '(') {
                ops.push_back(c);
            } else if (c == '0' || c == '1') {
                nums.emplace_back(c - '0', 1);
            } else if (c == '&' || c == '|') {
                while (!ops.empty() && (ops.back() == '&' || ops.back() == '|')) {
                    merge(ops.back());
                    ops.pop_back();
                }
                ops.push_back(c);
            } else {
                while (ops.back() != '(') {
                    merge(ops.back());
                    ops.pop_back();
                }
                ops.pop_back();
            }
        }
        while (!ops.empty()) {
            merge(ops.back());
            ops.pop_back();
        }
        return nums[0].second;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
func minOperationsToFlip(expression string) int {
    type pair struct{ val, cost int }
    nums := make([]pair, 0)
    ops := make([]byte, 0)
    merge := func(op byte) {
        b := nums[len(nums)-1]
        a := nums[len(nums)-2]
        nums = nums[:len(nums)-2]
        v1, c1, v2, c2 := a.val, a.cost, b.val, b.cost
        val, cost := 0, 0
        if op == '&' {
            val = v1 & v2
            if v1 == 1 && v2 == 1 {
                cost = min(c1, c2)
            } else if v1 == 0 && v2 == 0 {
                cost = min(c1+c2, 1+min(c1, c2))
            } else if v1 == 0 {
                cost = min(c1, 1)
            } else {
                cost = min(c2, 1)
            }
        } else {
            val = v1 | v2
            if v1 == 0 && v2 == 0 {
                cost = min(c1, c2)
            } else if v1 == 1 && v2 == 1 {
                cost = min(c1+c2, 1+min(c1, c2))
            } else if v1 == 1 {
                cost = min(c1, 1)
            } else {
                cost = min(c2, 1)
            }
        }
        nums = append(nums, pair{val, cost})
    }
    for i := 0; i < len(expression); i++ {
        c := expression[i]
        if c == '(' {
            ops = append(ops, c)
        } else if c == '0' || c == '1' {
            nums = append(nums, pair{int(c - '0'), 1})
        } else if c == '&' || c == '|' {
            for len(ops) > 0 && (ops[len(ops)-1] == '&' || ops[len(ops)-1] == '|') {
                merge(ops[len(ops)-1])
                ops = ops[:len(ops)-1]
            }
            ops = append(ops, c)
        } else {
            for ops[len(ops)-1] != '(' {
                merge(ops[len(ops)-1])
                ops = ops[:len(ops)-1]
            }
            ops = ops[:len(ops)-1]
        }
    }
    for len(ops) > 0 {
        merge(ops[len(ops)-1])
        ops = ops[:len(ops)-1]
    }
    return nums[0].cost
}

Comments