Skip to content

640. Solve the Equation

Description

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.

Solutions

Solution 1: Mathematics

Thinking

A linear equation must be reduced to \(ax+b=0\). Coefficients may be omitted and signs abut, so an ad-hoc scan is error-prone.

Split on =. On each side, scan signed terms: a trailing x updates the coefficient, otherwise the constant. Compare both sides to report infinite, none, or the unique integer root.

We split the \(equation\) by the equal sign "=" into left and right expressions, and compute the coefficient of "x" (denoted \(x_i\)) and the constant value (denoted \(y_i\)) for each side.

The equation is then transformed into: \(x_1 \times x + y_1 = x_2 \times x + y_2\).

  • When \(x_1 = x_2\): if \(y_1 \neq y_2\), there is no solution; if \(y_1 = y_2\), there are infinite solutions.
  • When \(x_1 \neq x_2\): there is a unique solution \(x = \frac{y_2 - y_1}{x_1 - x_2}\).

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)}'

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func solveEquation(equation string) string {
    f := func(s string) []int {
        x, y := 0, 0
        if s[0] != '-' {
            s = "+" + s
        }
        i, n := 0, len(s)
        for i < n {
            sign := 1
            if s[i] == '-' {
                sign = -1
            }
            i++
            j := i
            for j < n && s[j] != '+' && s[j] != '-' {
                j++
            }
            v := s[i:j]
            if s[j-1] == 'x' {
                a := 1
                if len(v) > 1 {
                    a, _ = strconv.Atoi(v[:len(v)-1])
                }
                x += sign * a
            } else {
                a, _ := strconv.Atoi(v)
                y += sign * a
            }
            i = j
        }
        return []int{x, y}
    }

    es := strings.Split(equation, "=")
    a, b := f(es[0]), f(es[1])
    x1, y1 := a[0], a[1]
    x2, y2 := b[0], b[1]
    if x1 == x2 {
        if y1 == y2 {
            return "Infinite solutions"
        } else {
            return "No solution"
        }
    }
    return fmt.Sprintf("x=%d", (y2-y1)/(x1-x2))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function solveEquation(equation: string): string {
    const [left, right] = equation.split('=');
    const createExpr = (s: string) => {
        let x = 0;
        let n = 0;
        let i = 0;
        let sym = 1;
        let cur = 0;
        let isX = false;
        for (const c of s) {
            if (c === '+' || c === '-') {
                if (isX) {
                    if (i === 0 && cur === 0) {
                        cur = 1;
                    }
                    x += cur * sym;
                } else {
                    n += cur * sym;
                }
                isX = false;
                cur = 0;
                i = 0;
                if (c === '+') {
                    sym = 1;
                } else {
                    sym = -1;
                }
            } else if (c === 'x') {
                isX = true;
            } else {
                i++;
                cur *= 10;
                cur += Number(c);
            }
        }
        if (isX) {
            if (i === 0 && cur === 0) {
                cur = 1;
            }
            x += cur * sym;
        } else {
            n += cur * sym;
        }
        return [x, n];
    };
    const lExpr = createExpr(left);
    const rExpr = createExpr(right);
    if (lExpr[0] === rExpr[0]) {
        if (lExpr[1] !== rExpr[1]) {
            return 'No solution';
        }
        return 'Infinite solutions';
    }
    return `x=${(lExpr[1] - rExpr[1]) / (rExpr[0] - lExpr[0])}`;
}

Comments