Domain 2MediumCORE

Solve the Equation

We are given a string representing a linear equation involving a single variable x and integer constants. The goal is to solve for x.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math

640. Solve the Equation

Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 42.8%


Problem Breakdown

We are given a string representing a linear equation involving a single variable x and integer constants. The goal is to solve for x.

Inputs: A string containing +, -, x, digits, and exactly one = sign. Outputs: A string indicating the solution (“x=#value”), “No solution”, or “Infinite solutions”.

Implicit Constraints & Edge Cases:

  1. Implicit Coefficients: Terms like x imply a coefficient of 1, while -x implies -1.
  2. Implicit Constants: A term like 5 is a constant, not an x term.
  3. No Spaces: The input string typically does not contain spaces (though handling them is trivial).
  4. Integer Solutions: If a unique solution exists, the problem guarantees x is an integer.
  5. Overflow: Python handles large integers automatically, so standard overflow checks aren’t needed for logic, but we must ensure we don’t divide by zero.

Intuition

A brute-force approach would be to iterate through possible integer values of x, substitute them into the equation, and check if LHS equals RHS. However, since the range of integers is infinite (or at least very large), this is O(∞)O(\infty) or impractical.

The key insight is that this is a linear equation of the form Ax+B=Cx+DAx + B = Cx + D. We can treat the left-hand side (LHS) and right-hand side (RHS) independently.

  1. Parse the LHS to find the total coefficient of x (AA) and the sum of constants (BB).
  2. Parse the RHS to find the total coefficient of x (CC) and the sum of constants (DD).
  3. Rearrange the equation: (A−C)x=D−B(A - C)x = D - B.
  4. Let TotalX=A−CTotalX = A - C and TotalConst=D−BTotalConst = D - B. The equation simplifies to TotalX⋅x=TotalConstTotalX \cdot x = TotalConst.

From here, we can determine the solution state based on TotalXTotalX:

  • If TotalX=0TotalX = 0 and TotalConst=0TotalConst = 0, every value of x works →\rightarrow “Infinite solutions”.
  • If TotalX=0TotalX = 0 and TotalConst≠0TotalConst \neq 0, no value satisfies the equation →\rightarrow “No solution”.
  • If TotalX≠0TotalX \neq 0, there is exactly one solution →x=TotalConst/TotalX\rightarrow x = TotalConst / TotalX.

Approach

  1. Split the Equation: Use split('=') to separate the string into left and right parts.
  2. Parse Function: Create a helper function (or logic) that takes a side of the equation and returns (x_coefficient, constant_sum).
    • Iterate through characters maintaining a current_sign (+1 or -1).
    • Accumulate digits into a current_number.
    • If ‘x’ is encountered: add sign * current_number (defaulting current_number to 1 if no digit was seen) to the x coefficient. Reset current_number.
    • If ’+’ or ’-’ is encountered: update current_sign.
    • At the end of the string, if a current_number exists, add it to the constant sum.
  3. Combine Results: Subtract RHS coefficients from LHS coefficients to move all terms to one side.
  4. Determine Output: Apply the logic derived in the Intuition section to return the correct string.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of the input string. We traverse the string once to parse coefficients and constants.
  • Space Complexity: O(1)O(1). We use a fixed amount of extra space for variables (coefficients, signs), regardless of input size.

Solution

def solveEquation(equation: str) -> str:
    # Split equation into left and right sides
    left, right = equation.split('=')
    
    def parse_side(side):
        x_coeff = 0
        const_sum = 0
        current_num = 0
        sign = 1
        
        for char in side:
            if char.isdigit():
                current_num = (current_num * 10) + int(char)
            elif char == 'x':
                # If no number was accumulated, coefficient is 1
                coeff = current_num if current_num else 1
                x_coeff += sign * coeff
                current_num = 0
            elif char == '+':
                sign = 1
            elif char == '-':
                sign = -1
        
        # Handle the last constant term if it exists (e.g., "x+5")
        if current_num > 0:
            const_sum += sign * current_num
            
        return x_coeff, const_sum

    x_l, c_l = parse_side(left)
    x_r, c_r = parse_side(right)
    
    # Move all x terms to left and constants to right: (x_l - x_r)x = c_r - c_l
    total_x = x_l - x_r
    total_const = c_r - c_l
    
    if total_x == 0:
        if total_const == 0:
            return "Infinite solutions"
        else:
            return "No solution"
    else:
        # Problem guarantees integer solution for unique case
        return f"x={total_const // total_x}"

Edge Cases Handled

  • Implicit Coefficients: Logic handles x (coeff 1) and -x (coeff -1) by checking if current_num is zero before multiplying.
  • Negative Signs: The sign variable tracks the operator preceding a number or x, correctly handling cases like -2x+3.
  • No Solution / Infinite Solutions: Explicitly checks if total_x is zero to distinguish between identity (0=00=0) and contradiction (0=50=5).
  • Trailing Constants: The final check if current_num > 0 ensures constants at the end of a side (e.g., in “x+5”) are added to the sum.