1896. Minimum Cost to Change the Final Value of Expression LeetCode Solution
In this guide, you will get 1896. Minimum Cost to Change the Final Value of Expression LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Change the Final Value of Expression problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Cost to Change the Final Value of Expression
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.
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).
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1896. Minimum Cost to Change the Final Value of Expression LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
1896. Minimum Cost to Change the Final Value of Expression LeetCode Solution in Java
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();
}
} // code provided by PROGIEZ
1896. Minimum Cost to Change the Final Value of Expression LeetCode Solution in Python
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] # code by PROGIEZ
