Problem Explanation

Given a Boolean expression, the problem asks to calculate the minimum operations needed to flip or change the final output of the expression. Here, an operation is defined as replacing '&' with '|', or '| with &', or flipping '0' to '1' or '1' to '0'. Parentheses are evaluated first and then calculation is done from left to right.

Example

1
2python
3Input: "(0&0)&(0&0&0)"
4Output: 3

How did we get 3? Here, three operations are needed:

• Convert the first '0' to '1'. The expression becomes "(1&0)&(0&0&0)".
• Convert the second '0' after '&' to '1'. The expression becomes "(1&1)&(0&0&0)".
• Convert the third '0' after '&' to '1'. The expression becomes "(1&1)&(1&0&0)".

Thus, changing those three zeros to ones will result in the final value being 1.

Solution Approach

To solve this problem, we are using a stack data structure to maintain the changing states of the expression. We make use of three stacks, one for storing the result values, second for storing the minimal operations needed, and the third for storing operators.

As we parse through the expression, we push characters onto the stack. Each time we encounter a closing parenthesis or a digit, we pop from the stack and calculate corresponding costs.

ASCII illustration of the stack after three replacements:

1
2
3stack after 1 operation -> [ '1', '1&0']
4stack after 2 operations -> [ '1&1', '1&0']
5stack after 3 operations -> [ '1&1&1', '0' ]

Python Solution

1
2python
3from typing import List
4
5class Solution:
6    def minOperationsToFlip(self, expression: str) -> int:
7        stack = []
8        for char in expression:
9            if char in ('0', '1', '|', '&'):
10                stack.append((char, 1 if char in '01' else 0))
11            elif char == '(':
12                stack.append(char)
13            else:
14                e2 = stack.pop()
15                stack.pop()
16                e1 = stack.pop()
17                if e2[0] == '0' and e1[0] == '|':
18                    stack.append(('0', 1))
19                else:
20                    stack.append((max(e1, e2, key=lambda x: (x[0] == '1', -x[1]))))
21        while len(stack) > 1:
22            e2 = stack.pop()
23            op = stack.pop()
24            e1 = stack.pop()
25            if e2[0] == e1[0]:
26                stack.append((e2[0], 1 + min(e1[1], e2[1])))
27            else:
28                stack.append((e2[0] if op[0] == '|' else e1[0], max(e1[1], e2[1])))
29        return stack[0][1]

Explanation:

The Python solution uses stack to solve the problem. Looping through the expression, when '0', '1', '|’, '&' are encountered, they are pushed onto the stack. When closing parenthesis is encountered it pops the last two expressions and decides the new expression and corresponding cost. The decision is made based on the bitwise rule. It then pushes the resulting expression back to the stack. We need to make sure that we handle case of braces and nested expressions separately. Hence, in the end of process, if the stack has more than one element, we pop out last two expressions and an operator, decide the cumulative expression and push it back to the stack. When there's only a single element left in the stack, we return its cost.

I encourage you to go through this problem with a debugger to understand it better. The stack is a great tool to "visualize" the state at each step.

Prime your brain and happy coding!# JavaScript Solution

1
2javascript
3class Solution {
4    minOperationsToFlip = function(expression) {
5        let chars = expression.split('');
6        let stack = [];
7        let map = {'0': '1', '1': '0', '&': '|', '|': '&'};
8  
9        for (let char of chars){
10            if (char === ')'){
11                let newStack = [];
12  
13                while (stack[stack.length - 1] !== '('){
14                    newStack.push(stack.pop());
15                }   
16  
17                stack.pop();
18                stack.push(this.getOperationsNeeded(newStack.reverse()));
19            } else{
20                stack.push(char);
21            }
22        } 
23        
24        return this.getOperationsNeeded(stack);
25    };
26  
27    getOperationsNeeded = function(chars){
28        let map = {'0': '1', '1': '0', '&': '|', '|': '&'};
29        let cost = new Map();
30        cost.set('0', [0, 1]);
31        cost.set('1', [1, 0]);
32  
33        let operations = [chars[0]];
34        for (let i = 2; i < chars.length; i += 2){
35            [operations[0], operations[1]] = this.getUpdatedCosts(chars[i - 1], operations, cost.get(chars[i]));
36        }
37        
38        return map[operations[0]] + String(Math.max(operations[1], 1));
39    }
40  
41    getUpdatedCosts = function(op, ops1, ops2){
42        let map = {'0': '1', '1': '0', '&': '|', '|': '&'};
43  
44        if (ops1[0] === ops2[0]){
45            return [ops1[0], Math.min(ops1[1], ops2[1]) + 1];
46        }
47  
48        if (op === '|'){
49            return [map[ops1[0]], Math.max(ops1[1], ops2[1])];
50        } else{
51            return [ops1[0], Math.max(ops1[1], ops2[1] + 1)];
52        }
53    }
54}

Explanation:

The JavaScript solution uses a similar approach to the Python solution. It splits the input string into an array of characters and initializes a stack to hold the characters. A 'map' is created to make character replacements when needed. It then iterates through each character in the array and if a closing parenthesis is encountered, it pops all the characters from the stack until an opening parenthesis is found and pushed onto a new stack. It then replaces the earlier pushed characters with the minimum number of operations required to change the final result of the popped characters and pushes it back into the original stack. The getOperationsNeeded method is used to calculate the minimum number of operations needed to change the value of characters through the getUpdatedCosts method depending on the operators and digits encountered. This continues until all characters are traversed and finally returns the number of operations needed, which should be only the last element left in the stack.

Java Solution

1
2java
3import java.util.Stack;
4
5class Solution {
6    public int minOperationsToFlip(String expression) {
7        Stack<Integer> stack = new Stack<>();
8        int n = expression.length();
9        for(int i = 0; i < n; ++i){
10            if(expression.charAt(i) == '0' || expression.charAt(i) == '1'){
11                stack.push(expression.charAt(i) - '0');
12            }
13            else if(expression.charAt(i) == '&'){
14                stack.push(-2);
15            }
16            else if(expression.charAt(i) == '|'){
17                stack.push(-1);
18            }
19            else if(expression.charAt(i) == ')'){
20                int b = stack.pop();
21                while(stack.peek() < 0){
22                    int op = stack.pop();
23                    int a = stack.pop();
24                    if(op == -1){
25                        int r = a | b;
26                        stack.push(r);
27                        b = r == 0 ? 2 : 1;
28                    }
29                    else{
30                        int r = a & b;
31                        stack.push(r);
32                        b = r == 1 ? 2 : 1;
33                    }
34                }
35                stack.pop();
36                stack.push(b);
37            }
38        }
39        int b = stack.pop();
40        int ans = 0;
41        while(!stack.isEmpty()){
42            int op = stack.pop();
43            int a = stack.pop();
44            if(op == -1){
45                ans = Math.max(Math.min(a, b), ans);
46            }
47            else{
48                ans = Math.max(Math.min(a, 2 - b), ans);
49            }
50            b = Math.min(a, b);
51        }
52        return ans;
53    }
54}

Explanation:

The Java solution follows a similar approach as the Python and JavaScript solutions. It uses a Stack data structure to store characters of the Boolean expression. This solution process '0', '1', '(', '|' and '&' in the same way as the previous solutions.

This solution uses an while loop to process closing parenthesis ')'. In the while loop, it continues to pop elements from stack until an open parenthesis '(' is encountered. According to the 'op' value, it calculates the result and then pushes it back to the stack.

Finally, after the whole expression gets parsed, the solution pops remaining elements from the stack and calculates the final minimum operations required accordingly. This process continues until the stack gets empty. The final answer is returned as the minimum operations required to flip the expression.

Solution Implementation