We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Change the Final Value of Expression

Difficulty: Hard

Problem Description

You are given a valid boolean expression as a string consisting of the characters '1', '0', '&', '|', '(', and ')'. Return the minimum cost to change the final value of the expression. The cost is defined as the number of operations needed to change '1' to '0', '0' to '1', '&' to '|', or '|' to '&'.

Key Insights

  • The expression must be evaluated in a specific order: parentheses first, then left-to-right.
  • The final value of the expression can be either 0 or 1.
  • Changing an operand or operator incurs a cost, and the goal is to minimize this cost to achieve the desired final value.
  • Dynamic programming can be used to calculate the minimum cost for sub-expressions.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a dynamic programming approach. We will maintain two 2D arrays (or dictionaries) to keep track of the minimum cost to make a sub-expression evaluate to 0 or 1. The expression will be parsed recursively, and for each sub-expression, we will calculate the costs based on the operators and their associated costs. The final result will be determined by evaluating the entire expression.

  1. Parse the expression and handle parentheses.
  2. For each operator ('&' or '|'), compute the costs for all combinations of its left and right operands.
  3. Use the results from the sub-expressions to build up the costs for larger sub-expressions.
  4. The final answer will be the minimum cost to change the whole expression to the desired value.

Code Solutions

def minCostToChange(expression: str) -> int:
    n = len(expression)
    dp = {}
    
    def dfs(start, end):
        if (start, end) in dp:
            return dp[(start, end)]
        
        if expression[start] == '1':
            return (1, 0)  # cost to make it 0, cost to make it 1
        if expression[start] == '0':
            return (0, 1)  # cost to make it 0, cost to make it 1
        
        min_cost_0, min_cost_1 = float('inf'), float('inf')
        i = start + 1
        
        while i <= end:
            if expression[i] in '&|':
                left_cost_0, left_cost_1 = dfs(start + 1, i - 1)
                right_cost_0, right_cost_1 = dfs(i + 1, end)
                
                if expression[i] == '&':
                    min_cost_0 = min(min_cost_0, left_cost_0 + right_cost_0)
                    min_cost_1 = min(min_cost_1, left_cost_1 + right_cost_1,
                                     left_cost_0 + right_cost_1 + 1, 
                                     left_cost_1 + right_cost_0 + 1)
                else:  # expression[i] == '|'
                    min_cost_0 = min(min_cost_0, left_cost_0 + right_cost_0 + 1, 
                                     left_cost_0 + right_cost_1 + 1, 
                                     left_cost_1 + right_cost_0 + 1)
                    min_cost_1 = min(min_cost_1, left_cost_1 + right_cost_1)
            i += 1
        
        dp[(start, end)] = (min_cost_0, min_cost_1)
        return dp[(start, end)]
    
    return min(dfs(0, n - 1))
← Back to All Questions