# LeetCode 640: Solve the Equation

## Problem Restatement

We are given a linear equation as a string.

The equation contains:

| Token | Meaning |
|---|---|
| `x` | The variable |
| integers | Constant terms or coefficients |
| `+` and `-` | Operations |
| `=` | Separates left and right sides |

We need to solve for `x`.

Return one of three possible answers:

| Case | Return |
|---|---|
| Exactly one solution | `"x=#value"` |
| No solution | `"No solution"` |
| Infinite solutions | `"Infinite solutions"` |

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

| Item | Meaning |
|---|---|
| Input | A string `equation` |
| Output | A string describing the solution |
| Equation type | Linear equation in one variable |
| Unique solution | Guaranteed to be integer |

Example function shape:

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

## Examples

Example 1:

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

Left side:

```text
x + 5 - 3 + x = 2x + 2
```

Right side:

```text
6 + x - 2 = x + 4
```

So the equation becomes:

```text
2x + 2 = x + 4
```

Move terms:

```text
x = 2
```

Output:

```python
"x=2"
```

Example 2:

```python
equation = "x=x"
```

Both sides are always equal for every value of `x`.

Output:

```python
"Infinite solutions"
```

Example 3:

```python
equation = "x=x+2"
```

This simplifies to:

```text
0 = 2
```

That is impossible.

Output:

```python
"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:

| Value | Meaning |
|---|---|
| `x_coeff` | Total coefficient of `x` |
| `constant` | Total constant value |

For example:

```python
"x+5-3+x"
```

becomes:

| Part | Value |
|---|---:|
| `x_coeff` | `2` |
| `constant` | `2` |

## Key Insight

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

```text
x_coeff * x + constant
```

If the left side gives:

```text
left_x * x + left_const
```

and the right side gives:

```text
right_x * x + right_const
```

then:

```text
left_x * x + left_const = right_x * x + right_const
```

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

```text
(left_x - right_x) * x = right_const - left_const
```

Let:

```python
coeff = left_x - right_x
const = right_const - left_const
```

Then:

| Case | Meaning | Result |
|---|---|---|
| `coeff == 0` and `const == 0` | `0 = 0` | Infinite solutions |
| `coeff == 0` and `const != 0` | `0 = nonzero` | No solution |
| `coeff != 0` | Unique solution | `x = const / coeff` |

## Parsing One Side

To parse a side like:

```python
"-x+5-12x+3"
```

we read one term at a time.

Each term has:

| Term | Meaning |
|---|---|
| `x` | coefficient `1` |
| `-x` | coefficient `-1` |
| `2x` | coefficient `2` |
| `-12x` | coefficient `-12` |
| `5` | constant `5` |
| `-3` | constant `-3` |

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

```python
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:

```python
parse_side(side)
```

returns:

```python
(x_coeff, constant)
```

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

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

Now every term starts with either `+` or `-`.

We read the sign:

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

Then we scan until the next sign:

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

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

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

The special case is plain `x`.

```python
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:

```python
constant += sign * int(term)
```

After parsing both sides, we solve:

```python
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:

```python
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:

```text
x_coeff * x + constant
```

Let the left side reduce to:

```text
left_x * x + left_const
```

and the right side reduce to:

```text
right_x * x + right_const
```

The original equation is equivalent to:

```text
left_x * x + left_const = right_x * x + right_const
```

Moving terms gives:

```text
(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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each character is scanned a constant number of times |
| Space | `O(n)` | Splitting and temporary term strings may use linear space |

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

```python
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:

| Test | Why |
|---|---|
| `"x+5-3+x=6+x-2"` | Standard sample with terms on both sides |
| `"x=x"` | Infinite solutions |
| `"2x=x"` | Solution is zero |
| `"2x+3x-6x=x+2"` | Negative result |
| `"x=x+2"` | No solution |
| `"-x=-1"` | Handles negative implicit coefficient |
| `"10x+5=5"` | Multi-digit coefficient |