Skip to content

640. Solve the Equation 👎

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  string solveEquation(string equation) {
    const string lhsEquation = equation.substr(0, equation.find('='));
    const string rhsEquation = equation.substr(equation.find('=') + 1);
    const auto& [lhsCoefficient, lhsConstant] = calculate(lhsEquation);
    const auto& [rhsCoefficient, rhsConstant] = calculate(rhsEquation);
    const int coefficient = lhsCoefficient - rhsCoefficient;
    const int constant = rhsConstant - lhsConstant;

    if (coefficient == 0 && constant == 0)
      return "Infinite solutions";
    if (coefficient == 0 && constant != 0)
      return "No solution";
    return "x=" + to_string(constant / coefficient);
  }

 private:
  pair<int, int> calculate(const string& s) {
    int coefficient = 0;
    int constant = 0;
    int num = 0;
    int sign = 1;

    for (int i = 0; i < s.length(); ++i) {
      const char c = s[i];
      if (isdigit(c))
        num = num * 10 + (c - '0');
      else if (c == '+' || c == '-') {
        constant += sign * num;
        sign = c == '+' ? 1 : -1;
        num = 0;
      } else {
        if (i > 0 && num == 0 && s[i - 1] == '0')
          continue;
        coefficient += num == 0 ? sign : sign * num;
        num = 0;
      }
    }

    return {coefficient, constant + sign * num};
  }
};

 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
class Solution {
  public String solveEquation(String equation) {
    String[] equations = equation.split("=");
    int[] lhs = calculate(equations[0]);
    int[] rhs = calculate(equations[1]);
    int coefficient = lhs[0] - rhs[0];
    int constant = rhs[1] - lhs[1];

    if (coefficient == 0 && constant == 0)
      return "Infinite solutions";
    if (coefficient == 0 && constant != 0)
      return "No solution";
    return "x=" + constant / coefficient;
  }

  private int[] calculate(final String s) {
    int coefficient = 0;
    int constant = 0;
    int num = 0;
    int sign = 1;

    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (Character.isDigit(c))
        num = num * 10 + (c - '0');
      else if (c == '+' || c == '-') {
        constant += sign * num;
        sign = c == '+' ? 1 : -1;
        num = 0;
      } else {
        if (i > 0 && num == 0 && s.charAt(i - 1) == '0')
          continue;
        coefficient += num == 0 ? sign : sign * num;
        num = 0;
      }
    }

    return new int[] {coefficient, constant + sign * num};
  }
}

 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
class Solution:
  def solveEquation(self, equation: str) -> str:
    def calculate(s: str) -> tuple:
      coefficient = 0
      constant = 0
      num = 0
      sign = 1

      for i, c in enumerate(s):
        if c.isdigit():
          num = num * 10 + int(c)
        elif c in '+-':
          constant += sign * num
          sign = 1 if c == '+' else -1
          num = 0
        else:
          if i > 0 and num == 0 and s[i - 1] == '0':
            continue
          coefficient += sign if num == 0 else sign * num
          num = 0

      return coefficient, constant + sign * num

    lhsEquation, rhsEquation = equation.split('=')
    lhsCoefficient, lhsConstant = calculate(lhsEquation)
    rhsCoefficient, rhsConstant = calculate(rhsEquation)
    coefficient = lhsCoefficient - rhsCoefficient
    constant = rhsConstant - lhsConstant

    if coefficient == 0 and constant == 0:
      return "Infinite solutions"
    if coefficient == 0 and constant != 0:
      return "No solution"
    return "x=" + str(constant // coefficient)