LeetCode 640: Solve the Equation

Problem Restatement

We are given a linear equation as a string.

The equation contains:

We need to solve for x.

Return one of three possible answers:

If there is exactly one solution, the problem guarantees that the value of x is an integer. The equation contains only +, -, the variable x, and coefficients.

Input and Output

Example function shape:

def solveEquation(equation: str) -> str:
    ...

Examples

Example 1:

equation = "x+5-3+x=6+x-2"

Left side:

x + 5 - 3 + x = 2x + 2

Right side:

6 + x - 2 = x + 4

So the equation becomes:

2x + 2 = x + 4

Move terms:

x = 2

Output:

"x=2"

Example 2:

equation = "x=x"

Both sides are always equal for every value of x.

Output:

"Infinite solutions"

Example 3:

equation = "x=x+2"

This simplifies to:

0 = 2

That is impossible.

Output:

"No solution"

First Thought: Move Terms While Scanning

We can scan the equation and try to move all x terms to one side and all constants to the other side directly.

That works, but it is easy to make sign mistakes after the = sign.

A cleaner method is to parse each side independently.

For each side, compute two values:

For example:

"x+5-3+x"

becomes:

Key Insight

Any side of the equation can be reduced into this form:

x_coeff * x + constant

If the left side gives:

left_x * x + left_const

and the right side gives:

right_x * x + right_const

then:

left_x * x + left_const = right_x * x + right_const

Move x terms to the left and constants to the right:

(left_x - right_x) * x = right_const - left_const

Let:

coeff = left_x - right_x
const = right_const - left_const

Then:

Parsing One Side

To parse a side like:

"-x+5-12x+3"

we read one term at a time.

Each term has:

A simple trick is to ensure every term starts with a sign.

If the expression does not start with + or -, prepend +.

Then scan from sign to sign.

Algorithm

1. Split the equation by =.
2. Parse the left side into (left_x, left_const).
3. Parse the right side into (right_x, right_const).
4. Compute:
   1. coeff = left_x - right_x
   2. const = right_const - left_const
5. If coeff == 0:
   1. If const == 0, return "Infinite solutions".
   2. Otherwise, return "No solution".
6. Otherwise, return "x=" + str(const // coeff).

Implementation

class Solution:
    def solveEquation(self, equation: str) -> str:
        def parse_side(side: str) -> tuple[int, int]:
            if side[0] not in "+-":
                side = "+" + side

            x_coeff = 0
            constant = 0
            i = 0

            while i < len(side):
                sign = 1 if side[i] == "+" else -1
                i += 1

                j = i
                while j < len(side) and side[j] not in "+-":
                    j += 1

                term = side[i:j]

                if term[-1] == "x":
                    coeff_text = term[:-1]

                    if coeff_text == "":
                        coeff = 1
                    else:
                        coeff = int(coeff_text)

                    x_coeff += sign * coeff
                else:
                    constant += sign * int(term)

                i = j

            return x_coeff, constant

        left, right = equation.split("=")

        left_x, left_const = parse_side(left)
        right_x, right_const = parse_side(right)

        coeff = left_x - right_x
        const = right_const - left_const

        if coeff == 0:
            if const == 0:
                return "Infinite solutions"
            return "No solution"

        return "x=" + str(const // coeff)

Code Explanation

The helper function:

parse_side(side)

returns:

(x_coeff, constant)

For easier parsing, we add a leading sign when needed:

if side[0] not in "+-":
    side = "+" + side

Now every term starts with either + or -.

We read the sign:

sign = 1 if side[i] == "+" else -1

Then we scan until the next sign:

while j < len(side) and side[j] not in "+-":
    j += 1

If the term ends with x, it contributes to the x coefficient:

if term[-1] == "x":

The special case is plain x.

coeff_text = term[:-1]

If coeff_text is empty, the coefficient is 1.

Otherwise, the coefficient is the integer before x.

For constants, we add the signed integer:

constant += sign * int(term)

After parsing both sides, we solve:

coeff = left_x - right_x
const = right_const - left_const

If coeff is zero, the equation no longer contains x.

So it either has infinite solutions or no solution.

Otherwise, the solution is:

const // coeff

Correctness

The parser processes each side term by term. Every term is either an x term or a constant term. For an x term, the parser adds its signed coefficient to x_coeff. For a constant term, it adds its signed value to constant. Therefore, each side is reduced exactly to:

x_coeff * x + constant

Let the left side reduce to:

left_x * x + left_const

and the right side reduce to:

right_x * x + right_const

The original equation is equivalent to:

left_x * x + left_const = right_x * x + right_const

Moving terms gives:

(left_x - right_x) * x = right_const - left_const

The algorithm computes these two values as coeff and const.

If coeff == 0 and const == 0, the equation becomes 0 = 0, so every value of x satisfies it.

If coeff == 0 and const != 0, the equation becomes 0 = const, which is impossible.

If coeff != 0, there is exactly one solution, and the problem guarantees that it is an integer. The algorithm returns that value.

Therefore, the algorithm returns the correct result for all valid inputs.

Complexity

Let n = len(equation).

The core state itself uses O(1) space.

Alternative: One-Pass With Side Sign

We can also parse the whole equation in one pass.

Before the =, terms keep their normal sign.

After the =, every term’s contribution is negated because it moves to the left side.

This can be slightly shorter, but the two-side parser is easier to reason about.

Testing

def run_tests():
    s = Solution()

    assert s.solveEquation("x+5-3+x=6+x-2") == "x=2"
    assert s.solveEquation("x=x") == "Infinite solutions"
    assert s.solveEquation("2x=x") == "x=0"
    assert s.solveEquation("2x+3x-6x=x+2") == "x=-1"
    assert s.solveEquation("x=x+2") == "No solution"
    assert s.solveEquation("-x=-1") == "x=1"
    assert s.solveEquation("10x+5=5") == "x=0"

    print("all tests passed")

run_tests()

Test meaning: