# Solve the Equation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/solve-the-equation)
Canonical: https://scaleengineer.com/dsa/problems/solve-the-equation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
---
## Problem
Solve a given equation and return the value of `'x'` in the form of a string `"x=#value"`. The equation contains only `'+'`, `'-'` operation, the variable `'x'` and its coefficient. You should return `"No solution"` if there is no solution for the equation, or `"Infinite solutions"` if there are infinite solutions for the equation.

If there is exactly one solution for the equation, we ensure that the value of `'x'` is an integer.

**Example 1:**

**Input:** equation = "x+5-3+x=6+x-2"
**Output:** "x=2"

**Example 2:**

**Input:** equation = "x=x"
**Output:** "Infinite solutions"

**Example 3:**

**Input:** equation = "2x=x"
**Output:** "x=0"

**Constraints:**

* `3 <= equation.length <= 1000`
* `equation` has exactly one `'='`.
* `equation` consists of integers with an absolute value in the range `[0, 100]` without any leading zeros, and the variable `'x'`.
* The input is generated that if there is a single solution, it will be an integer.

# Approaches
## Regex-based Term Parsing
This approach involves breaking down the equation into its left and right sides. For each side, we can use string manipulation techniques, such as splitting by a regular expression, to isolate each term (e.g., `+x`, `-5`, `+2x`). A helper function then processes these terms to compute the total coefficient of 'x' and the sum of the constant values. Finally, we solve the simplified linear equation.
**Time:** O(N), where N is the length of the equation string. The `split` operation takes O(N) time, and iterating through the resulting terms also takes O(N) time in total. · **Space:** O(N), where N is the length of the equation string. This is because we create an array of strings to hold the terms, and the total size of these strings is proportional to the input size.
**Pros:** Conceptually straightforward, leveraging built-in string functionalities.; The logic is relatively easy to follow and implement correctly.
**Cons:** Higher space complexity due to the creation of an intermediate array of strings for the terms.; String splitting and regular expressions can have a higher constant factor overhead compared to direct manual parsing.
### Explanation
The core idea is to parse each side of the equation to find the sum of x-coefficients and the sum of constants. We can achieve this by splitting the expression string into terms.

- **Algorithm**

- Split the input `equation` string at the `'='` character to get the left-hand side (LHS) and right-hand side (RHS).
- Define a helper function, `evaluate(expression)`, that takes a string expression and returns a pair of integers: `[total_x_coefficient, total_constant_sum]`.
- Inside `evaluate`, use a regular expression or string splitting to break the expression into individual terms. A good method is to split the string using a positive lookahead `(?=[+-])`, which splits at `+` or `-` but keeps them as part of the following term. This results in an array of terms like `["x", "+5", "-3", "+x"]`.
- Iterate through the array of terms. For each term:
  - If it contains `'x'`, parse its coefficient. Note that `"x"` implies a coefficient of `+1`, and `"-x"` implies `-1`. Add this coefficient to the `total_x_coefficient`.
  - If it does not contain `'x'`, it's a constant. Parse it as an integer and add it to the `total_constant_sum`.
- Call the `evaluate` function on both the LHS and RHS strings.
- Let the results be `[lhs_x, lhs_const]` and `[rhs_x, rhs_const]`.
- Rearrange the equation to the form `Ax = B`. The final coefficient of `x` is `x_coeff = lhs_x - rhs_x`, and the final constant value is `const_val = rhs_const - lhs_const`.
- Analyze the results:
  - If `x_coeff` is 0 and `const_val` is 0, the equation is `0 = 0`, which means there are infinite solutions.
  - If `x_coeff` is 0 and `const_val` is not 0, the equation is `0 = non-zero`, which is a contradiction, meaning no solution.
  - If `x_coeff` is not 0, there is a unique solution `x = const_val / x_coeff`.

- **Code Snippet**

```java
class Solution {
    public String solveEquation(String equation) {
        String[] parts = equation.split("=");
        int[] left = evaluate(parts[0]);
        int[] right = evaluate(parts[1]);

        int xCoeff = left[0] - right[0];
        int constVal = right[1] - left[1];

        if (xCoeff == 0) {
            if (constVal == 0) {
                return "Infinite solutions";
            } else {
                return "No solution";
            }
        } else {
            return "x=" + (constVal / xCoeff);
        }
    }

    private int[] evaluate(String expr) {
        int xCoeff = 0;
        int constSum = 0;
        String[] terms = expr.split("(?=[+-])");
        for (String term : terms) {
            if (term.equals("+") || term.equals("-")) continue;
            if (term.contains("x")) {
                String coeffPart = term.substring(0, term.length() - 1);
                if (coeffPart.isEmpty() || coeffPart.equals("+")) {
                    xCoeff++;
                } else if (coeffPart.equals("-")) {
                    xCoeff--;
                } else {
                    xCoeff += Integer.parseInt(coeffPart);
                }
            } else {
                constSum += Integer.parseInt(term);
            }
        }
        return new int[]{xCoeff, constSum};
    }
}
```
### Algorithm
- Split the input `equation` string at the `'='` character to get the left-hand side (LHS) and right-hand side (RHS).
- Define a helper function, `evaluate(expression)`, that takes a string expression and returns a pair of integers: `[total_x_coefficient, total_constant_sum]`.
- Inside `evaluate`, use a regular expression or string splitting to break the expression into individual terms. A good method is to split the string using a positive lookahead `(?=[+-])`, which splits at `+` or `-` but keeps them as part of the following term. This results in an array of terms like `["x", "+5", "-3", "+x"]`.
- Iterate through the array of terms. For each term:
  - If it contains `'x'`, parse its coefficient. Note that `"x"` implies a coefficient of `+1`, and `"-x"` implies `-1`. Add this coefficient to the `total_x_coefficient`.
  - If it does not contain `'x'`, it's a constant. Parse it as an integer and add it to the `total_constant_sum`.
- Call the `evaluate` function on both the LHS and RHS strings.
- Let the results be `[lhs_x, lhs_const]` and `[rhs_x, rhs_const]`.
- Rearrange the equation to the form `Ax = B`. The final coefficient of `x` is `x_coeff = lhs_x - rhs_x`, and the final constant value is `const_val = rhs_const - lhs_const`.
- Analyze the results:
  - If `x_coeff` is 0 and `const_val` is 0, the equation is `0 = 0`, which means there are infinite solutions.
  - If `x_coeff` is 0 and `const_val` is not 0, the equation is `0 = non-zero`, which is a contradiction, meaning no solution.
  - If `x_coeff` is not 0, there is a unique solution `x = const_val / x_coeff`.

## Single-Pass Manual Parsing
This approach improves efficiency by parsing the equation in a single pass without relying on regular expressions or creating intermediate data structures. We iterate through each side of the equation character by character, maintaining state such as the current number being formed and the sign of the term. This allows us to directly compute the total 'x' coefficients and constant sums, leading to lower memory usage and potentially faster execution.
**Time:** O(N), where N is the length of the equation. We perform a single pass over the string for each side of the equation. · **Space:** O(1). We only use a few variables to store the current state of the parsing (coefficients, sums, sign, current number), regardless of the input string's length.
**Pros:** Highly efficient in terms of space, using only a constant amount of extra memory.; Generally faster due to avoiding the overhead of regex engines and intermediate object creation.
**Cons:** The parsing logic is more intricate and requires careful state management (current number, sign, etc.).; It can be more prone to implementation errors if edge cases (like implicit coefficients or starting signs) are not handled carefully.
### Explanation
Instead of splitting the string into an array of terms, we can process it character by character, which is more efficient in terms of memory.

- **Algorithm**

- Split the equation at the `'='` to get LHS and RHS strings.
- Define a helper function `evaluate(expression)` that parses the expression in a single pass without creating intermediate collections.
- Inside `evaluate`, initialize variables: `x_coeff = 0`, `const_sum = 0`, `sign = 1` (for the current term's sign), and `current_num = 0` (for the number being parsed).
- Iterate through the expression string character by character from left to right.
- At each character:
  - If it's a digit, update `current_num` by appending the digit's value (e.g., `current_num = current_num * 10 + digit`).
  - If it's an `'x'`, this marks an x-term. The coefficient is the `current_num` parsed so far (or 1 if no number was parsed, e.g., for `"+x"`). Add `sign * coefficient` to `x_coeff`. Reset `current_num` for the next term.
  - If it's a `'+'` or `'-'`, this signifies the end of the previous term (which must be a constant). Add `sign * current_num` to `const_sum`. Then, reset `current_num` and update the `sign` for the upcoming term.
- After the loop finishes, the last parsed number needs to be added to the `const_sum`.
- Call `evaluate` for both LHS and RHS.
- Combine the results and determine the solution using the same logic as the first approach.

- **Code Snippet**

```java
class Solution {
    public String solveEquation(String equation) {
        String[] parts = equation.split("=");
        int[] left = evaluate(parts[0]);
        int[] right = evaluate(parts[1]);

        int xCoeff = left[0] - right[0];
        int constVal = right[1] - left[1];

        if (xCoeff == 0) {
            return constVal == 0 ? "Infinite solutions" : "No solution";
        } else {
            return "x=" + (constVal / xCoeff);
        }
    }

    private int[] evaluate(String expr) {
        int xCoeff = 0;
        int constSum = 0;
        int sign = 1;
        int currentNum = 0;
        boolean hasNum = false;

        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);
            if (Character.isDigit(c)) {
                currentNum = currentNum * 10 + (c - '0');
                hasNum = true;
            } else if (c == 'x') {
                xCoeff += sign * (hasNum ? currentNum : 1);
                currentNum = 0;
                hasNum = false;
            } else { // c is '+' or '-'
                constSum += sign * currentNum;
                sign = (c == '+') ? 1 : -1;
                currentNum = 0;
                hasNum = false;
            }
        }
        // Add the last number if it exists
        constSum += sign * currentNum;
        
        return new int[]{xCoeff, constSum};
    }
}
```
### Algorithm
- Split the equation at the `'='` to get LHS and RHS strings.
- Define a helper function `evaluate(expression)` that parses the expression in a single pass without creating intermediate collections.
- Inside `evaluate`, initialize variables: `x_coeff = 0`, `const_sum = 0`, `sign = 1` (for the current term's sign), and `current_num = 0` (for the number being parsed).
- Iterate through the expression string character by character from left to right.
- At each character:
  - If it's a digit, update `current_num` by appending the digit's value (e.g., `current_num = current_num * 10 + digit`).
  - If it's an `'x'`, this marks an x-term. The coefficient is the `current_num` parsed so far (or 1 if no number was parsed, e.g., for `"+x"`). Add `sign * coefficient` to `x_coeff`. Reset `current_num` for the next term.
  - If it's a `'+'` or `'-'`, this signifies the end of the previous term (which must be a constant). Add `sign * current_num` to `const_sum`. Then, reset `current_num` and update the `sign` for the upcoming term.
- After the loop finishes, the last parsed number needs to be added to the `const_sum`.
- Call `evaluate` for both LHS and RHS.
- Combine the results and determine the solution using the same logic as the first approach.

# Solutions
### Java

```java
class Solution {
public
  String solveEquation(String equation) {
    String[] es = equation.split("=");
    int[] a = f(es[0]), b = f(es[1]);
    int x1 = a[0], y1 = a[1];
    int x2 = b[0], y2 = b[1];
    if (x1 == x2) {
      return y1 == y2 ? "Infinite solutions" : "No solution";
    }
    return "x=" + (y2 - y1) / (x1 - x2);
  }
private
  int[] f(String s) {
    int x = 0, y = 0;
    if (s.charAt(0) != '-') {
      s = "+" + s;
    }
    int i = 0, n = s.length();
    while (i < n) {
      int sign = s.charAt(i) == '+' ? 1 : -1;
      ++i;
      int j = i;
      while (j < n && s.charAt(j) != '+' && s.charAt(j) != '-') {
        ++j;
      }
      String v = s.substring(i, j);
      if (s.charAt(j - 1) == 'x') {
        x += sign * (v.length() > 1
                         ? Integer.parseInt(v.substring(0, v.length() - 1))
                         : 1);
      } else {
        y += sign * Integer.parseInt(v);
      }
      i = j;
    }
    return new int[]{x, y};
  }
}

```

### Python

```python
class Solution:
    def solveEquation(self, equation: str) -> str: def f(s): x = y = 0 if s[0] != '-': s = '+' + s i, n = 0, len(s) while i < n: sign = 1 if s[i] == '+' else - 1 i += 1 j = i while j < n and s[j] not in '+-': j += 1 v = s[i: j] if v[- 1] == 'x': x += sign * (int(v[: - 1]) if len(v) > 1 else 1) else: y += sign * int(v) i = j return x, y a, b = equation . split('=') x1, y1 = f(a) x2, y2 = f(b) if x1 == x2: return 'Infinite solutions' if y1 == y2 else 'No solution' return f 'x= { ( y2 - y1 ) // ( x1 - x2 ) } '

```