LeetCode Solutions Blog

Solve the Equation

Difficulty: Medium

Problem Description

Given an equation in the form of a string that contains the variable 'x' and its coefficients, solve for 'x' and return the result in the form of "x=#value". If there is no solution, return "No solution", and if there are infinite solutions, return "Infinite solutions".

Key Insights

The equation can be split into two parts: left-hand side (LHS) and right-hand side (RHS) using the '=' character.
Each side can contain terms with 'x' and constant integers.
We need to collect the coefficients of 'x' and the constant terms separately from both sides.
The final result will depend on whether the coefficients and constant terms allow for a unique solution, no solution, or infinite solutions.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the equation string. We traverse the string a limited number of times. Space Complexity: O(1), since we are using a fixed amount of additional space for counting coefficients and constants.

Solution

To solve the equation, we will:

Split the equation into LHS and RHS at the '=' character.
Parse both sides to calculate the total coefficient of 'x' and the total constant value.
Compare the results to determine if there's a unique solution, no solution, or infinite solutions.

Code Solutions

def solveEquation(equation: str) -> str:
    # Split the equation into left and right parts
    left, right = equation.split('=')
    
    # Function to parse one side of the equation
    def parse_side(side):
        x_coeff = 0
        constant = 0
        i = 0
        n = len(side)
        sign = 1  # 1 for positive, -1 for negative
        
        while i < n:
            if side[i] in ['+', '-']:
                sign = 1 if side[i] == '+' else -1
                i += 1
            
            # Read the coefficient
            coeff = 0
            while i < n and side[i].isdigit():
                coeff = coeff * 10 + int(side[i])
                i += 1
            
            # If 'x' follows the coefficient
            if i < n and side[i] == 'x':
                x_coeff += sign * (coeff if coeff != 0 else 1)
                i += 1
            else:
                constant += sign * coeff
        
        return x_coeff, constant
    
    # Parse both sides
    lhs_x, lhs_const = parse_side(left)
    rhs_x, rhs_const = parse_side(right)
    
    # Combine the results
    total_x = lhs_x - rhs_x
    total_const = rhs_const - lhs_const
    
    # Determine the result
    if total_x == 0:
        if total_const == 0:
            return "Infinite solutions"
        else:
            return "No solution"
    else:
        return f"x={total_const // total_x}"

# Example usage
print(solveEquation("x+5-3+x=6+x-2"))  # Output: "x=2"