Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable x and its coefficient.



If there is no solution for the equation, return "No solution".


If there are infinite solutions for the equation, return "Infinite solutions".


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


Example 1:

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



Example 2:

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



Example 3:

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



Example 4:

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



Example 5:

Input: "x=x+2"
Output: "No solution"

Difficulty: interview

Starter code:

class Solution:
    def solveEquation(self, equation: str) -> str:
        

Solutions:
class Solution:
     def calc(self, part):
         part += "+" ## added tmp symbol in the end to sum last item within the loop
         start = x = n = 0
         coeff = 1
         for end, char in enumerate(part):
             # print("charIdx:", equation[end], "char: ", char, char == "+" or char == "-", "slice: ", equation[start:end])
             if char == "+" or char == "-":
                 var = part[start:end]
                 if var == "":
                     continue
                 if "x" in var:
                     var = var[:-1]
                     if var in ["", "+"]:
                         var = 1
                     elif var == "-":
                         var = -1
                     x += int(var) * coeff
                     start = end
                 else:
                     n += int(var) * coeff
                     start = end
         return x, n
     
     def solveEquation(self, equation):
         """
         :type equation: str
         :rtype: str
         """
         # how big is N
         # time vs. space complexity?
         
         # split by "=" to left and right; time complexity: O(N)
         # sums Xs and consts on both sides (left and right)
         # take a difference b/w the sides' sums
         # simplify dividing by X's coeff
         # if x==0 and n==0 on the other - infinite
         # if x==0 and a constant on the other - no solution
         # if x on one side, and a constant on the other - solution
         
         # test: 2-x+2x-x-x+1=x
         # test2: "x+5-3+x=6+x-2"
         # test2: "+5-3+x=6+x-2"
         # -x=-1
         
         left, right = equation.split("=")
         x1, n1 = self.calc(left) # O(leftN)
         x2, n2 = self.calc(right) # O(rightN)
         x, n = x1 - x2, n1 - n2
         n = n / x if (x != 0) else n
         x = 1 if (x != 0) else x
         if x == 0 and n != 0:
             return "No solution"
         if x == 0 and n == 0:
             return "Infinite solutions"
         return "x={}".format(int(-n))
         
         # time complexity O(N)


class Solution:
     def solveEquation(self, equation):
         """
         :type equation: str
         :rtype: str
         """
         left_x = right_x = 0
         left_const = right_const = 0
         
         cur_left = True
         cur_num = 0
         cur_sign = 1
         has_num = False
         for c in equation:
             if c == "=":
                 left_const += cur_num * cur_sign
                 cur_num = 0
                 cur_sign = 1
                 cur_left = False
                 has_num = False
             elif c in '+-':
                 if cur_left:
                     left_const += cur_num * cur_sign
                 else:
                     right_const += cur_num * cur_sign
                 cur_num = 0
                 cur_sign = 1 if c == '+' else -1
                 has_num = False
             elif c == 'x':
                 if cur_left:
                     left_x += cur_sign* (cur_num if has_num else 1)
                 else:
                     right_x += cur_sign* (cur_num if has_num else 1)
                 cur_num = 0
                 has_num = False
             else:
                 cur_num = cur_num * 10 + int(c)
                 has_num = True
             
             # print(left_x, right_x, left_const, right_const, cur_num, cur_sign)
         
         right_const += cur_num*cur_sign
         left_x -= right_x
         right_const -= left_const
         
         if left_x == 0 and right_const == 0:
             return "Infinite solutions"
         elif left_x == 0 and right_const != 0:
             return "No solution"
         else:
             return "x=" + str(int(right_const/left_x))

class Solution:
     def solveEquation(self, equation):
         l, r = equation.split("=")
         ret = self.compute(l)
         lnum, lx = ret[0], ret[1]
         ret = self.compute(r)
         rnum, rx = ret[0], ret[1]
         if lx == rx and lnum - rnum == 0:
             return "Infinite solutions"
         elif lx == rx and lnum - rnum != 0:
             return "No solution"
         else:
             if rx > lx:
                 return "x=" + str(int((lnum - rnum)/(rx - lx)))
             else:
                 return "x=" + str(int((rnum - lnum)/(lx - rx)))
             
         print((lx, lnum))
         
     def compute(self, eq):
         val = ''
         s = '+'
         eq =  eq + '+'
         num, x = 0,0
         for c in eq:
             if c == 'x':
                 if val == '':
                     val = '1'
                 if s =='+':
                     x += int(val)
                 else:
                     x -= int(val)
                 val = ''
             elif c == '+' or c == '-':
                 if val != '' and s == '+':
                     num += int(val)
                 elif val != '' and s == '-':
                     num -= int(val)
                 s = c
                 val = ''
 
             else:
                 val += c
         return num, x


class Solution:
     lx = 0
     lc = 0
     rx = 0
     rc = 0
     def solveEquation(self, equation):
         """
         :type equation: str
         :rtype: str
         """
         self.lx = 0
         self.lc = 0
         self.rx = 0
         self.rc = 0
         size = len(equation)
         l=0 
         r=0
         left=True
         for i in range(1,size):
             #print(i)
             if equation[i] == "=":
                 l=r
                 r=i+1
                 self.lastEq(equation[l:r-1],left)
                 left=False
                 continue
             if equation[i] in {"+","-"}:
                 if equation[r:i] in {"+","-",""}:
                     continue
                 l=r
                 r=i
                 self.lastEq(equation[l:r],left)
             if i == size-1:
                 l=r
                 r=i
                 self.lastEq(equation[l:r+1],left)
             
         #print(str(self.lx)+"x"+" "+str(self.lc) +" = " + str(self.rx) + "x " + str(self.rc))
         x = self.lx-self.rx
         c = self.rc - self.lc
         if x == 0 and c == 0:
             return "Infinite solutions"
         if x == 0:
             return "No solution"
         return "x="+str(int(c/x))
     
     def lastEq(self,s,left):
         print(s)
         if "x" in s:
             if s[0]!='-':
                 if left:
                     if s in {"x","+x"}:
                         self.lx+=1
                     else:
                         self.lx += float(s[:-1])
                 else:
                     if s in {"x","+x"}:
                         self.rx+=1
                     else:
                         self.rx += float(s[:-1])
             else:
                 if left:
                     if s in {"x","-x"}:
                         self.lx-=1
                     else:
                         self.lx -= float(s[1:-1])
                 else:
                     if s in {"x","-x"}:
                         self.rx-=1
                     else:
                         self.rx -= float(s[1:-1])
         else:
             if s[0]!='-':
                 if left:
                     self.lc += float(s)
                 else:
                     self.rc += float(s)
             else:
                 if left:
                     self.lc -= float(s[1:])
                 else:
                     self.rc -= float(s[1:])
         print((str(self.lx)+"x"+" "+str(self.lc) +" = " + str(self.rx) + "x " + str(self.rc)))


class Solution:
     def solveEquation(self, equation):
         """
         :type equation: str
         :rtype: str
         """
         count_x = count_integer = 0
         left, right = equation.replace('-', ' -').replace('+', ' +').split('=')
         left_items = left.lstrip().split(' ')
         right_items = right.lstrip().split(' ')
         for l in left_items:
             if l[-1] == 'x':
                 if l[:-1] == '' or l[:-1] == '+':
                     count_x += 1
                 elif l[:-1] == '-':
                     count_x -= 1
                 else:
                     count_x += int(l[:-1])
             else:
                 count_integer -= int(l)
         for r in right_items:
             if r[-1] == 'x':
                 if r[:-1] == '' or r[:-1] == '+':
                     count_x -= 1
                 elif r[:-1] == '-':
                     count_x += 1
                 else:
                     count_x -= int(r[:-1])
             else:
                 count_integer += int(r)
         if count_x == 0 and count_integer != 0:
             return 'No solution'
         elif count_x == 0 and count_integer == 0:
             return 'Infinite solutions'
         else:
             return 'x=' + str(int(count_integer / count_x))


import re
 class Solution:
     def solveEquation(self, equation):
         """
         :type equation: str
         :rtype: str
         """
         # Gets sum of x's in an eq
         def get_x_sum(s):
 
             total = 0
             curr = ""
             sign = "+"
             for c in s:
                 if c == "x":
                     if curr == "":
                         total += int(sign+"1")
                     else:
                         total += int(sign+curr)
                 elif c == "+" or c == "-":
                     curr = ""
                     sign = c
                 else:
                     curr += c
             
             return total
         
         # Gets sum of ints in an eq
         def get_int_sum(s):
             total = 0
             curr = ""
             sign = "+"
             for c in s:
                 if c == "x":
                     curr = ""
                     sign = "+"
                 elif c == "+" or c == "-":
                     if curr != "":
                         total += int(sign+curr)
                         curr = ""
                     sign = c
                 else:
                     curr += c
             
             if curr != "":
                 total += int(sign+curr)
             return total
             
         lhs,rhs = equation.split("=")
         
         lhs_sum_x = get_x_sum(lhs)
         lhs_sum_int = get_int_sum(lhs)
         rhs_sum_x = get_x_sum(rhs)
         rhs_sum_int = get_int_sum(rhs)
         
         if lhs_sum_int == rhs_sum_int:
             if lhs_sum_x == rhs_sum_x:
                 return "Infinite solutions"
             return "x=0"
         else:
             if lhs_sum_x == rhs_sum_x:
                 return "No solution"
             
             diff_x = lhs_sum_x-rhs_sum_x
             diff_int = rhs_sum_int - lhs_sum_int
             return "x=" + str(diff_int // diff_x)
             
             
         
         
         


class Solution:
     def solveEquation(self, equation):
         """
         :type equation: str
         :rtype: str
         """
         a=0
         b=0
         coeff=''
         right=1
         for i in equation+'+':
             if (i=='+' or i=='-' or i=='=') and coeff!='':
                 if 'x' in coeff:
                     coeff=coeff.strip('x')
                     if coeff=='-':
                         a-= right
                     elif coeff=='+' or coeff=='':
                         a+= right
                     else:
                         a+= (int(coeff.strip('x'))*right)
                 else:
                     b-= (int(coeff)*right)
                 coeff=i
                 if i=='=':
                     right=-1
                     coeff=''
             else:
                 coeff+=i
 #            print(i,a,b,coeff)
         if a==0 and b==0:
             return "Infinite solutions"
         elif a==0:
             return "No solution"
         elif b==0:
             return "x=0"
         else:
             return "x="+str(int(b/a))


class Solution:
     def solveEquation(self, equation):
         """
         :type equation: str
         :rtype: str
         """
         [left,right]=equation.split('=')
         l=[0,0]
         temp=''
         flag=1
         if left[0]=='-':
             flag=-1
             left=left[1:]
         for i in left:
             if i!='+' and i!='-':temp+=i
             else:
                 if temp[-1]!='x':
                     l[1]+=flag*int(temp)
                 else:
                     if len(temp)==1:l[0]+=flag
                     else:l[0]+=flag*int(temp[:-1])
                 if i=='+':flag=1
                 if i=='-':flag=-1
                 temp=''
                 print(l)
         if temp[-1]!='x':
             l[1]+=flag*int(temp)
         else:
             if len(temp)==1:l[0]+=flag
             else:l[0]+=flag*int(temp[:-1])
         temp=''
         r=[0,0]
         flag=1
         if right[0]=='-':
             flag=-1
             right=right[1:]
         for i in right:
             if i!='+' and i!='-':temp+=i
             else:
                 if temp[-1]!='x':
                     r[1]+=flag*int(temp)
                 else:
                     if len(temp)==1:r[0]+=flag
                     else:r[0]+=flag*int(temp[:-1])
                 if i=='+':flag=1
                 if i=='-':flag=-1
                 temp=''
         if temp[-1]!='x':
             r[1]+=flag*int(temp)
         else:
             if len(temp)==1:r[0]+=flag
             else:r[0]+=flag*int(temp[:-1])
         temp=''
         print(l,r)
         if l[0]==r[0]:
             if l[1]==r[1]:return 'Infinite solutions'
             else:return 'No solution'
         else:
             ans=int((r[1]-l[1])/(l[0]-r[0]))
             return 'x='+str(ans)