Hex.*

LC640 - Solve the Equation

Posted on In
Datastructure and Algorithm: DAY 71. Leetcode: 248/2736

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:

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

Example 2:

1
2
Input: equation = "x=x"
Output: "Infinite solutions"

Example 3:

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

Constraints:

1
2
3
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'.

Solution

  1. Move all expressions to the left
  2. Then all minus signs are preceded by a plus sign as a prefix
  3. Divide the equation by plus sign
  4. Count the number of x and the operation result of the number
  5. Get results based on the requirements
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
class Solution:
    def solveEquation(self, equation: str) -> str:
        left, right = equation.split("=")
        new_left = []
        new_right = []
        if right[0] != "-":
            right = "+" + right

        for i in range(len(left)):
            if left[i] == "-":
                new_left.append("+-")
            else:
                new_left.append(left[i])
        for i in range(len(right)):
            if right[i] == "+":
                new_right.append("+-")
            elif right[i] == "-":
                new_right.append("+")
            else:
                new_right.append(right[i])
        e = "".join(new_left)+"".join(new_right)

        print(e.split("+"))
        
        letter = 0
        num = 0
        for cur in e.split("+"):
            sign, coe, l = 1, 0, 0
            if cur:
                if cur[0] == "-":
                    sign = -1
                    if cur[-1] == "x":
                        coe = int(cur[1:-1]) if len(cur) > 2 else 1
                        letter += sign * coe
                    else:
                        num += int(cur)
                else:
                    if cur[-1] == "x":
                        coe = int(cur[:-1]) if len(cur) > 1 else 1
                        letter += sign * coe
                    else:
                        num += int(cur)
           
        if letter == num == 0:
            return "Infinite solutions"
        elif letter == 0 and num != 0:
            return "No solution"
        else:
            v = int(-num / letter)
            return "x="+str(v)