LeetCode 1896 - Minimum Cost to Change the Final Value of Expression

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming, Stack

Solution

Problem Understanding

This problem gives us a boolean expression containing only:

'0' and '1'
binary operators '&' and '|'
parentheses

The expression is guaranteed to be valid, which means every operator has valid operands and every parenthesis is properly matched.

The important detail is that the expression is not evaluated using normal operator precedence. Instead:

Parentheses are evaluated first.
Everything else is evaluated strictly from left to right.

For example:

1|1&0

is evaluated as:

(1|1)&0 = 1&0 = 0

not:

1|(1&0) = 1

The goal is to determine the minimum number of operations required to flip the final value of the expression.

Allowed operations are:

Change '0' to '1'
Change '1' to '0'
Change '&' to '|'
Change '|' to '&'

Each operation costs exactly 1.

The expression length can be as large as 10^5, so we need a very efficient algorithm. Any exponential or quadratic exploration of all possible modifications will be too slow.

A naive implementation could easily fail because:

Expressions can be deeply nested.
Left-to-right evaluation changes how operators interact.
A local change can affect the global result.
Sometimes changing an operator is cheaper than changing operands.
Sometimes flipping a deeply nested subexpression is optimal.

Another important observation is that we are not asked to construct the modified expression. We only need the minimum number of operations.

Edge cases include:

A single digit like "0" or "1"
Very deep parentheses nesting
Long chains such as "1|0|1|0|1"
Cases where changing an operator is cheaper than changing operands
Cases where flipping one subexpression automatically changes the whole result

Because the expression is valid and fully parenthesized where needed, we can safely parse it using stacks.

Approaches

Brute Force Approach

A brute force solution would try every possible modification sequence until the final expression value flips.

For each character in the expression, we could:

Keep it unchanged
Flip a digit
Flip an operator

We would then evaluate the resulting expression and track the minimum number of modifications that changes the final value.

This approach is theoretically correct because it explores all possible transformed expressions. Eventually it would find the optimal one.

However, this is completely impractical.

If the expression has length n, then each mutable character introduces multiple possibilities. The number of transformed expressions becomes exponential. Even evaluating each candidate expression costs additional time.

With n up to 100000, brute force is impossible.

Key Insight

The crucial observation is that for every subexpression, we only need two pieces of information:

its current boolean value
the minimum cost required to flip that value

Instead of exploring every transformed expression, we compute these values incrementally while parsing the expression.

For example, suppose we know:

left subexpression evaluates to 0 and costs 2 to flip
right subexpression evaluates to 1 and costs 1 to flip

Then we can determine:

the result of left & right
the minimum cost to flip that result

using local rules.

This transforms the problem into a dynamic programming style parsing problem.

We process the expression using stacks:

one stack for operands
one stack for operators

Each operand stores:

(current_value, min_cost_to_flip)

When we combine two operands with an operator, we compute the resulting pair.

Because each character is processed only once, the solution becomes linear.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all modifications
Optimal	O(n)	O(n)	Stack-based parsing with DP state

Algorithm Walkthrough

State Definition

For every subexpression, we store:

(value, flip_cost)

Where:

value is the evaluated result, either 0 or 1
flip_cost is the minimum operations needed to change this subexpression into the opposite value

Examples:

"0" -> (0, 1)
"1" -> (1, 1)

A single digit always costs 1 to flip.

Step 1: Initialize Stacks

We use:

values stack for (value, flip_cost)
operators stack for '&', '|', '('

Step 2: Process the Expression Left to Right

We iterate through every character.

If the character is:

'0' or '1'
push its state onto values
'&', '|', or '('
push onto operators
')'
resolve everything until '('

Step 3: Reduce Expressions

Whenever we have:

left operator right

we combine them into a new state.

Suppose:

left  = (lv, lc)
right = (rv, rc)

Step 4: Merge for AND

If operator is '&':

Result Value

lv & rv

Minimum Cost to Flip

If result is 1:

Both sides must currently be 1.

To make result 0, we can:

flip left
flip right
change operator to '|' and make one side 0

The optimal formula simplifies to:

min(lc, rc)

If result is 0:

To make result 1:

both operands must become 1
or operator changes to '|'

Formula:

if lv == 0 and rv == 0:
    min(lc + rc, 1 + min(lc, rc))
else:
    1

Step 5: Merge for OR

Symmetric logic applies.

If result is 0:

min(lc, rc)

If result is 1:

if lv == 1 and rv == 1:
    min(lc + rc, 1 + min(lc, rc))
else:
    1

Step 6: Handle Parentheses

When encountering ')', repeatedly evaluate until '(' is reached.

Step 7: Final Answer

After the full parse, one state remains.

Its flip_cost is the answer.

Why it works

For every subexpression, the algorithm maintains an invariant:

(value, flip_cost)

accurately represents:

the evaluated boolean value
the minimum operations needed to invert that value

Every merge operation considers all valid ways to flip the combined expression:

changing operands
changing operators
combinations of both

Because all possibilities are locally minimized and every subexpression is processed exactly once, the final result is globally optimal.

Python Solution

class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        values = []
        operators = []

        def apply():
            right_val, right_cost = values.pop()
            left_val, left_cost = values.pop()
            op = operators.pop()

            if op == '&':
                value = left_val & right_val

                if value == 1:
                    cost = min(left_cost, right_cost)
                else:
                    if left_val == 0 and right_val == 0:
                        cost = min(
                            left_cost + right_cost,
                            1 + min(left_cost, right_cost)
                        )
                    else:
                        cost = 1

            else:
                value = left_val | right_val

                if value == 0:
                    cost = min(left_cost, right_cost)
                else:
                    if left_val == 1 and right_val == 1:
                        cost = min(
                            left_cost + right_cost,
                            1 + min(left_cost, right_cost)
                        )
                    else:
                        cost = 1

            values.append((value, cost))

        for ch in expression:
            if ch == '0':
                values.append((0, 1))

            elif ch == '1':
                values.append((1, 1))

            elif ch in '&|(':
                operators.append(ch)

            elif ch == ')':
                while operators and operators[-1] != '(':
                    apply()

                operators.pop()

            else:
                while (
                    operators
                    and operators[-1] in '&|'
                ):
                    apply()

                operators.append(ch)

            while (
                len(values) >= 2
                and operators
                and operators[-1] in '&|'
            ):
                apply()

        while operators:
            apply()

        return values[-1][1]

The implementation uses two stacks to simulate expression evaluation.

The values stack stores tuples:

(value, flip_cost)

Each tuple summarizes everything necessary about a subexpression.

The apply() helper pops:

the right operand
the left operand
the operator

and computes the merged state.

The logic inside apply() directly encodes the minimum-cost transition rules for AND and OR operations.

The main parsing loop processes the expression character by character.

Digits immediately become states:

(0, 1)
(1, 1)

Operators and parentheses are handled similarly to classical infix expression evaluation.

Whenever enough information is available to evaluate an expression, apply() is called.

At the end, the remaining tuple contains the full expression result and the minimum cost to flip it.

Go Solution

type State struct {
	value int
	cost  int
}

func minOperationsToFlip(expression string) int {
	values := []State{}
	operators := []byte{}

	apply := func() {
		right := values[len(values)-1]
		values = values[:len(values)-1]

		left := values[len(values)-1]
		values = values[:len(values)-1]

		op := operators[len(operators)-1]
		operators = operators[:len(operators)-1]

		value := 0
		cost := 0

		if op == '&' {
			value = left.value & right.value

			if value == 1 {
				if left.cost < right.cost {
					cost = left.cost
				} else {
					cost = right.cost
				}
			} else {
				if left.value == 0 && right.value == 0 {
					a := left.cost + right.cost

					b := left.cost
					if right.cost < b {
						b = right.cost
					}
					b += 1

					if a < b {
						cost = a
					} else {
						cost = b
					}
				} else {
					cost = 1
				}
			}

		} else {
			value = left.value | right.value

			if value == 0 {
				if left.cost < right.cost {
					cost = left.cost
				} else {
					cost = right.cost
				}
			} else {
				if left.value == 1 && right.value == 1 {
					a := left.cost + right.cost

					b := left.cost
					if right.cost < b {
						b = right.cost
					}
					b += 1

					if a < b {
						cost = a
					} else {
						cost = b
					}
				} else {
					cost = 1
				}
			}
		}

		values = append(values, State{
			value: value,
			cost:  cost,
		})
	}

	for i := 0; i < len(expression); i++ {
		ch := expression[i]

		if ch == '0' {
			values = append(values, State{0, 1})

		} else if ch == '1' {
			values = append(values, State{1, 1})

		} else if ch == '&' || ch == '|' || ch == '(' {
			operators = append(operators, ch)

		} else if ch == ')' {
			for len(operators) > 0 &&
				operators[len(operators)-1] != '(' {
				apply()
			}

			operators = operators[:len(operators)-1]
		}

		for len(values) >= 2 &&
			len(operators) > 0 &&
			(operators[len(operators)-1] == '&' ||
				operators[len(operators)-1] == '|') {
			apply()
		}
	}

	for len(operators) > 0 {
		apply()
	}

	return values[len(values)-1].cost
}

The Go implementation follows the same stack-based design as the Python version.

The primary difference is that Go uses a custom State struct instead of tuples.

Slices are used as stacks:

append() pushes
slicing removes the top element

Go does not support nested helper functions that mutate outer variables as naturally as Python, but closures still work correctly here.

No integer overflow concerns exist because costs never exceed the expression length.

Worked Examples

Example 1

expression = "1&(0|1)"

Step-by-Step Trace

Character	Action	Values Stack	Operators Stack
`1`	push `(1,1)`	`[(1,1)]`	`[]`
`&`	push operator	`[(1,1)]`	`['&']`
`(`	push parenthesis	`[(1,1)]`	`['&','(']`
`0`	push `(0,1)`	`[(1,1),(0,1)]`	`['&','(']`
`	`	push operator	`[(1,1),(0,1)]`
`1`	push `(1,1)`	`[(1,1),(0,1),(1,1)]`	`['&','(','

Apply 0 | 1:

value = 1
flip cost = 1

Stacks become:

Values	Operators
`[(1,1),(1,1)]`	`['&','(']`

Encounter ):

Remove '('.

Apply 1 & 1:

value = 1
flip cost = 1

Final answer:

Example 2

expression = "(0&0)&(0&0&0)"

The left group:

0&0

evaluates to:

(0,2)

because changing to 1 requires either:

flipping both operands
or changing operator plus one operand

Minimum cost is 2.

The right group:

0&0&0

also evaluates to 0 with flip cost 2.

Final combination:

0 & 0

requires one more operation to become 1.

Total:

Example 3

expression = "(0|(1|0&1))"

Inner expression:

0&1

evaluates to:

with flip cost 1.

Then:

1|0

evaluates to:

with flip cost 1.

Finally:

0|1

evaluates to:

with flip cost 1.

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is pushed and popped at most once
Space	O(n)	Stacks may store the entire expression

The algorithm performs a single left-to-right pass through the expression.

Every operand and operator enters and leaves its stack at most one time. Therefore the total work is linear.

The stacks can grow proportionally to the nesting depth and expression size, giving linear auxiliary space usage.

Test Cases

sol = Solution()

# Provided examples
assert sol.minOperationsToFlip("1&(0|1)") == 1  # example 1
assert sol.minOperationsToFlip("(0&0)&(0&0&0)") == 3  # example 2
assert sol.minOperationsToFlip("(0|(1|0&1))") == 1  # example 3

# Single values
assert sol.minOperationsToFlip("0") == 1  # flip single digit
assert sol.minOperationsToFlip("1") == 1  # flip single digit

# Simple AND
assert sol.minOperationsToFlip("1&1") == 1  # flip one operand
assert sol.minOperationsToFlip("0&0") == 2  # both operands needed

# Simple OR
assert sol.minOperationsToFlip("0|0") == 1  # flip one operand
assert sol.minOperationsToFlip("1|1") == 2  # both operands needed

# Nested parentheses
assert sol.minOperationsToFlip("((1))") == 1  # redundant nesting
assert sol.minOperationsToFlip("(((0)))") == 1  # deep nesting

# Left-to-right evaluation
assert sol.minOperationsToFlip("1|1&0") == 1  # evaluated left-to-right

# Operator flip cheaper
assert sol.minOperationsToFlip("1&(1|0)") == 1  # flip operator

# Long chain
assert sol.minOperationsToFlip("0|0|0|0") == 1  # one change sufficient

# Mixed nesting
assert sol.minOperationsToFlip("(1&(0|1))|(0&1)") == 1  # mixed operations

Test Summary

Test	Why
`"1&(0	1)"`
`"(0&0)&(0&0&0)"`	Validates complex AND behavior
`"(0	(1
`"0"`	Smallest possible expression
`"1"`	Smallest true expression
`"1&1"`	AND producing true
`"0&0"`	AND requiring multiple flips
`"0	0"`
`"1	1"`
`"((1))"`	Deep parentheses handling
`"1	1&0"`
`"1&(1	0)"`
`"0	0
`"(1&(0	1))

Edge Cases

Single Character Expressions

Expressions like "0" or "1" are important because they contain no operators or parentheses. A parser that assumes every expression contains binary operations may fail here.

The implementation handles this naturally by pushing a single state onto the stack and returning its flip cost directly.

Deeply Nested Parentheses

Expressions such as:

"((((1))))"

can expose bugs in stack management and parenthesis handling.

The algorithm safely processes nested groups because '(' markers isolate subexpressions until the matching ')' is encountered.

Left-to-Right Evaluation

A major trap is assuming normal operator precedence.

For example:

1|1&0

must evaluate as:

(1|1)&0

not:

1|(1&0)

The implementation correctly enforces this by reducing operators immediately whenever possible, rather than giving & higher precedence.

Cases Where Operator Changes Are Optimal

Sometimes changing an operator is cheaper than modifying operands.

Example:

1&(0|1)

Changing | to & costs only 1, immediately flipping the final result.

The merge formulas explicitly consider operator modifications, ensuring the minimum cost is always found.