Skip to content

1896. Minimum Cost to Change the Final Value of Expression 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
62
63
64
class Solution {
 public:
  int minOperationsToFlip(string expression) {
    // [(the expression, the cost to toggle the expression)]
    stack<pair<char, int>> stack;
    pair<char, int> lastPair;

    for (const char e : expression) {
      if (e == '(' || e == '&' || e == '|') {
        // These aren't expressions, so the cost is meaningless.
        stack.push({e, 0});
        continue;
      }
      if (e == ')') {
        lastPair = stack.top();
        stack.pop();
        stack.pop();  // Pop '('.
      } else {        // e == '0' || e == '1'
        // Store the '0' or '1'. The cost to change their values is just 1,
        // whether it's changing '0' to '1' or '1' to '0'.
        lastPair = {e, 1};
      }
      if (!stack.empty() &&
          (stack.top().first == '&' || stack.top().first == '|')) {
        const char op = stack.top().first;
        stack.pop();
        const auto [a, costA] = stack.top();
        stack.pop();
        const auto [b, costB] = lastPair;
        // Determine the cost to toggle op(a, b).
        if (op == '&') {
          if (a == '0' && b == '0')
            // Change '&' to '|' and a|b to '1'.
            lastPair = {'0', 1 + min(costA, costB)};
          else if (a == '0' && b == '1')
            // Change '&' to '|'.
            lastPair = {'0', 1};
          else if (a == '1' && b == '0')
            // Change '&' to '|'.
            lastPair = {'0', 1};
          else  // a == '1' and b == '1'
            // Change a|b to '0'.
            lastPair = {'1', min(costA, costB)};
        } else {  // op == '|'
          if (a == '0' && b == '0')
            // Change a|b to '1'.
            lastPair = {'0', min(costA, costB)};
          else if (a == '0' && b == '1')
            // Change '|' to '&'.
            lastPair = {'1', 1};
          else if (a == '1' && b == '0')
            // Change '|' to '&'.
            lastPair = {'1', 1};
          else  // a == '1' and b == '1'
            // Change '|' to '&' and a|b to '0'.
            lastPair = {'1', 1 + min(costA, costB)};
        }
      }
      stack.push(lastPair);
    }

    return stack.top().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
class Solution {
  public int minOperationsToFlip(String expression) {
    // [(the expression, the cost to toggle the expression)]
    Deque<Pair<Character, Integer>> stack = new ArrayDeque<>();
    Pair<Character, Integer> lastPair = null;

    for (final char e : expression.toCharArray()) {
      if (e == '(' || e == '&' || e == '|') {
        // These aren't expressions, so the cost is meaningless.
        stack.push(new Pair<>(e, 0));
        continue;
      }
      if (e == ')') {
        lastPair = stack.pop();
        stack.pop(); // Pop '('.
      } else {       // e == '0' || e == '1'
        // Store the '0' or '1'. The cost to change their values is just 1,
        // whether it's changing '0' to '1' or '1' to '0'.
        lastPair = new Pair<>(e, 1);
      }
      if (!stack.isEmpty() && (stack.peek().getKey() == '&' || stack.peek().getKey() == '|')) {
        final char op = stack.pop().getKey();
        final char a = stack.peek().getKey();
        final int costA = stack.pop().getValue();
        final char b = lastPair.getKey();
        final int costB = lastPair.getValue();
        // Determine the cost to toggle op(a, b).
        if (op == '&') {
          if (a == '0' && b == '0')
            // Change '&' to '|' and a|b to '1'.
            lastPair = new Pair<>('0', 1 + Math.min(costA, costB));
          else if (a == '0' && b == '1')
            // Change '&' to '|'.
            lastPair = new Pair<>('0', 1);
          else if (a == '1' && b == '0')
            // Change '&' to '|'.
            lastPair = new Pair<>('0', 1);
          else // a == '1' and b == '1'
            // Change a|b to '0'.
            lastPair = new Pair<>('1', Math.min(costA, costB));
        } else { // op == '|'
          if (a == '0' && b == '0')
            // Change a|b to '1'.
            lastPair = new Pair<>('0', Math.min(costA, costB));
          else if (a == '0' && b == '1')
            // Change '|' to '&'.
            lastPair = new Pair<>('1', 1);
          else if (a == '1' && b == '0')
            // Change '|' to '&'.
            lastPair = new Pair<>('1', 1);
          else // a == '1' and b == '1'
            // Change '|' to '&' and a|b to '0'.
            lastPair = new Pair<>('1', 1 + Math.min(costA, costB));
        }
      }
      stack.push(lastPair);
    }

    return stack.peek().getValue();
  }
}

 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
class Solution:
  def minOperationsToFlip(self, expression: str) -> int:
    stack = []  # [(the expression, the cost to toggle the expression)]

    for e in expression:
      if e in '(&|':
        # These aren't expressions, so the cost is meaningless.
        stack.append((e, 0))
        continue
      if e == ')':
        lastPair = stack.pop()
        stack.pop()  # Pop '('.
      else:  # e == '0' or e == '1'
        # Store the '0' or '1'. The cost to change their values is just 1,
        # whether it's changing '0' to '1' or '1' to '0'.
        lastPair = (e, 1)
      if stack and stack[-1][0] in '&|':
        op = stack.pop()[0]
        a, costA = stack.pop()
        b, costB = lastPair
        # Determine the cost to toggle op(a, b).
        if op == '&':
          if a == '0' and b == '0':
            # Change '&' to '|' and a|b to '1'.
            lastPair = ('0', 1 + min(costA, costB))
          elif a == '0' and b == '1':
            # Change '&' to '|'.
            lastPair = ('0', 1)
          elif a == '1' and b == '0':
            # Change '&' to '|'.
            lastPair = ('0', 1)
          else:  # a == '1' and b == '1'
            # Change a|b to '0'.
            lastPair = ('1', min(costA, costB))
        else:  # op == '|'
          if a == '0' and b == '0':
            # Change a|b to '1'.
            lastPair = ('0', min(costA, costB))
          elif a == '0' and b == '1':
            # Change '|' to '&'.
            lastPair = ('1', 1)
          elif a == '1' and b == '0':
            # Change '|' to '&'.
            lastPair = ('1', 1)
          else:  # a == '1' and b == '1'
            # Change '|' to '&' and a|b to '0'.
            lastPair = ('1', 1 + min(costA, costB))
      stack.append(lastPair)

    return stack[-1][1]