LeetCode 640 - Solve the Equation

The problem is asking us to solve a linear equation containing a single variable 'x' and integer coefficients, expressed as a string. The equation may include addition '+', subtraction '-', and the equality operator '='.

leetcodemediummathstringsimulation

LeetCode Problem 640

Difficulty: 🟡 Medium
Topics: Math, String, Simulation

Solution

Problem Understanding

The problem is asking us to solve a linear equation containing a single variable 'x' and integer coefficients, expressed as a string. The equation may include addition '+', subtraction '-', and the equality operator '='. We need to parse this string, combine like terms, and solve for 'x'. The result should be returned as "x=#value" if there is a unique integer solution. If no solution exists, return "No solution", and if there are infinitely many solutions, return "Infinite solutions".

The input string has several constraints: it always contains exactly one '=', and the coefficients of 'x' are integers in the range [0, 100] without leading zeros. The maximum length of the string is 1000 characters, so we need a solution that can process strings efficiently without iterating exponentially over possibilities.

Important edge cases include equations where the 'x' terms cancel each other out, equations with zero coefficients, and equations where one side contains only constants. For example, "x=x" should return "Infinite solutions" and "2x=x" should return "x=0". Handling signs correctly when splitting terms is crucial.

Approaches

A brute-force approach would attempt to evaluate the equation for every possible integer value of 'x'. While this guarantees correctness if we search over a sufficiently large range, it is highly inefficient because the range could be large, and parsing and evaluating the expression repeatedly would be slow.

The optimal approach uses algebraic manipulation. We can treat the equation as two sides separated by '='. By parsing each side, we can extract the total coefficient of 'x' and the total constant term. Once we have ax + b = cx + d, we can solve for 'x' using x = (d - b) / (a - c). This works because it reduces the problem to basic arithmetic and string parsing, making it linear in the length of the input.

Approach Time Complexity Space Complexity Notes
Brute Force O(R * N) O(1) Evaluate all possible integer values of x in some range, inefficient for large coefficients.
Optimal O(N) O(1) Parse each term once, compute coefficients and constants, solve using algebra.

Algorithm Walkthrough

  1. Split the input string by '=' into the left-hand side (LHS) and right-hand side (RHS). This allows separate processing of both sides of the equation.
  2. Parse each side into terms. Terms are delimited by '+' or '-', and a term can be either a constant or an 'x' term with an optional coefficient.
  3. For each term, accumulate the total coefficient of 'x' and the total constant. For example, in "2x+3-x", the total coefficient of 'x' is 1 and the total constant is 3.
  4. After processing both sides, compute the net 'x' coefficient as lhs_x_coeff - rhs_x_coeff and the net constant as rhs_const - lhs_const.
  5. Handle edge cases. If the net 'x' coefficient is zero, then either there is no solution if the net constant is non-zero, or infinite solutions if the net constant is zero.
  6. Otherwise, compute the integer solution for 'x' as net_constant / net_x_coeff and return it in the format "x=#value".

Why it works: By combining like terms on both sides and reducing the equation to a standard linear form, we ensure that the solution is mathematically correct. Parsing each term ensures correct handling of signs and coefficients.

Python Solution

class Solution:
    def solveEquation(self, equation: str) -> str:
        def parse(expr: str) -> tuple[int, int]:
            i, n = 0, len(expr)
            x_coeff, const = 0, 0
            while i < n:
                sign = 1
                if expr[i] in '+-':
                    sign = 1 if expr[i] == '+' else -1
                    i += 1
                num = 0
                has_num = False
                while i < n and expr[i].isdigit():
                    num = num * 10 + int(expr[i])
                    i += 1
                    has_num = True
                if i < n and expr[i] == 'x':
                    x_coeff += sign * (num if has_num else 1)
                    i += 1
                else:
                    const += sign * num
            return x_coeff, const

        lhs, rhs = equation.split('=')
        lhs_x, lhs_const = parse(lhs)
        rhs_x, rhs_const = parse(rhs)

        net_x = lhs_x - rhs_x
        net_const = rhs_const - lhs_const

        if net_x == 0:
            if net_const == 0:
                return "Infinite solutions"
            else:
                return "No solution"
        return f"x={net_const // net_x}"

Implementation walkthrough: The parse function iterates over each character of an expression, correctly handling '+' and '-' signs, optional coefficients, and constants. After parsing both sides, we subtract coefficients and constants to simplify the equation. Finally, we check special cases for zero coefficients and compute the solution.

Go Solution

import "strconv"

func solveEquation(equation string) string {
    parse := func(expr string) (int, int) {
        xCoeff, constSum := 0, 0
        n := len(expr)
        i := 0
        for i < n {
            sign := 1
            if expr[i] == '+' || expr[i] == '-' {
                if expr[i] == '-' {
                    sign = -1
                }
                i++
            }
            num := 0
            hasNum := false
            for i < n && expr[i] >= '0' && expr[i] <= '9' {
                num = num*10 + int(expr[i]-'0')
                i++
                hasNum = true
            }
            if i < n && expr[i] == 'x' {
                if !hasNum {
                    num = 1
                }
                xCoeff += sign * num
                i++
            } else {
                constSum += sign * num
            }
        }
        return xCoeff, constSum
    }

    parts := []string{}
    for _, c := range equation {
        if c == '=' {
            parts = append(parts, "")
        } else {
            if len(parts) == 0 {
                parts = append(parts, "")
            }
            parts[len(parts)-1] += string(c)
        }
    }

    lhsX, lhsC := parse(parts[0])
    rhsX, rhsC := parse(parts[1])

    netX := lhsX - rhsX
    netC := rhsC - lhsC

    if netX == 0 {
        if netC == 0 {
            return "Infinite solutions"
        }
        return "No solution"
    }
    return "x=" + strconv.Itoa(netC/netX)
}

Go-specific notes: We explicitly convert characters to integers and handle string building for the two sides. Go lacks tuple return type destructuring like Python, but returning two values works similarly. We also handle integer conversion and string formatting using strconv.

Worked Examples

Example 1: "x+5-3+x=6+x-2"

Step LHS x-coeff LHS const RHS x-coeff RHS const
Parse "x+5-3+x" 2 2 - -
Parse "6+x-2" - - 1 4
Net values 2-1=1 4-2=2

Solution: x = 2/1 = 2, output "x=2"

Example 2: "x=x"

Step LHS x-coeff LHS const RHS x-coeff RHS const
Parse "x" 1 0 - -
Parse "x" - - 1 0
Net values 1-1=0 0-0=0

Since net_x = 0 and net_const = 0 → "Infinite solutions"

Example 3: "2x=x"

Step LHS x-coeff LHS const RHS x-coeff RHS const
Parse "2x" 2 0 - -
Parse "x" - - 1 0
Net values 2-1=1 0-0=0

Solution: x = 0/1 = 0, output "x=0"

Complexity Analysis

Measure Complexity Explanation
Time O(N) Each character is processed once when parsing LHS and RHS.
Space O(1) Only counters for x coefficients and constants are maintained; no additional data structures proportional to input size.

The complexity is linear because parsing and arithmetic operations scale directly with the length of the string. Memory usage is constant since we only track sums.

Test Cases

# Provided examples
assert Solution().solveEquation("x+5-3+x