2008. Minimum Cost to Change the Final Value of Expression
My accepted C++ solution to LeetCode problem 2008, Minimum Cost to Change the Final Value of Expression, running in 35ms.
- Difficulty: Hard
- C++
- Runtime 35ms
- Memory 17.6MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
C++
Accepted on LeetCode — runtime 35ms, memory 17.6MB, accepted 2025-12-27.
class Solution {
public:
int minOperationsToFlip(string expression) {
stack<pair<int,int>> vals;
stack<char> ops;
auto calc = [&]() {
auto [v2, c2] = vals.top(); vals.pop();
auto [v1, c1] = vals.top(); vals.pop();
char op = ops.top(); ops.pop();
if (op == '&') {
if (v1 == 1 && v2 == 1) vals.push({1, min(c1, c2)});
else if (v1 == 0 && v2 == 0) vals.push({0, min(c1, c2) + 1});
else vals.push({0, 1});
} else {
if (v1 == 0 && v2 == 0) vals.push({0, min(c1, c2)});
else if (v1 == 1 && v2 == 1) vals.push({1, min(c1, c2) + 1});
else vals.push({1, 1});
}
};
for (char c : expression) {
if (c == '0' || c == '1') {
vals.push({c - '0', 1});
} else if (c == '(') {
ops.push(c);
} else if (c == '&' || c == '|') {
while (!ops.empty() && ops.top() != '(') calc();
ops.push(c);
} else {
while (ops.top() != '(') calc();
ops.pop();
}
}
while (!ops.empty()) calc();
return vals.top().second;
}
};