Minimum Cost to Change the Final Value of Expression Solution in Java

Ah, the joys of logical expressions! You know, the kind that makes you question your life choices while trying to figure out if you need to flip a few bits to get the desired outcome. Imagine you’re at a party, and someone asks you to change the music from “Baby Shark” to “Bohemian Rhapsody.” You know it’s going to take some effort, but how much? That’s the essence of the Minimum Cost to Change the Final Value of Expression problem.

In this problem, you’re given a logical expression made up of 0s, 1s, &, |, and parentheses. Your task is to determine the minimum number of operations required to flip the final value of the expression. Sounds simple, right? Well, it’s like trying to convince your friend that pineapple belongs on pizza—it’s a lot more complicated than it seems!

C++ Solution
Python Solution

Java Code Solution


class Solution {
  public int minOperationsToFlip(String expression) {
    Deque> stack = new ArrayDeque<>();
    Pair lastPair = null;

    for (final char e : expression.toCharArray()) {
      if (e == '(' || e == '&' || e == '|') {
        stack.push(new Pair<>(e, 0));
        continue;
      }
      if (e == ')') {
        lastPair = stack.pop();
        stack.pop(); // Pop '('.
      } else {
        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();
        if (op == '&') {
          if (a == '0' && b == '0')
            lastPair = new Pair<>('0', 1 + Math.min(costA, costB));
          else if (a == '0' && b == '1')
            lastPair = new Pair<>('0', 1);
          else if (a == '1' && b == '0')
            lastPair = new Pair<>('0', 1);
          else
            lastPair = new Pair<>('1', Math.min(costA, costB));
        } else {
          if (a == '0' && b == '0')
            lastPair = new Pair<>('0', Math.min(costA, costB));
          else if (a == '0' && b == '1')
            lastPair = new Pair<>('1', 1);
          else if (a == '1' && b == '0')
            lastPair = new Pair<>('1', 1);
          else
            lastPair = new Pair<>('1', 1 + Math.min(costA, costB));
        }
      }
      stack.push(lastPair);
    }

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

Approach Explanation

The code uses a stack to keep track of the characters and their associated costs as it processes the expression. It evaluates the logical operations based on the current character and the last processed character, calculating the minimum cost to flip the expression as it goes. The key operations are handled based on whether the current operator is & or |, and the costs are updated accordingly.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(n), where n is the length of the expression. Each character is processed once.
Space Complexity O(n) in the worst case due to the stack storing pairs of characters and their costs.

Real-World Example

Imagine you’re trying to convince your friends to switch from their favorite TV show to a new one. Each friend has a different opinion (0 for “no” and 1 for “yes”), and you need to figure out the minimum number of arguments (flips) you need to change their minds. Just like in the expression, you have to consider the logical operations (like & for “all must agree” and | for “anyone can agree”) to find the best strategy.

Similar Problems