Simple Python via GCD


  • 1

    Here we handle numerators and denominators in two separate lists, find the least common multiple LCM for denoms and adjust numers based on it. Others are pretty straight forward.

    class Solution(object):
        def fractionAddition(self, s):
            """
            :type s: str
            :rtype: str
            """
            def gcd(a, b):                                  # compute greatest common divisor
                return a if not b else gcd(b, a%b)
            
            def lcm(a, b):                                  # compute least common multiple
                return a * b / gcd(a, b)
            
            i, n, turn, sign = 0, len(s), 1, 1
            numers, denoms = [], []                         # two separate lists store numerators and denominators
            while i < n:
                if s[i].isdigit():
                    j = i
                    while i < n and s[i].isdigit():
                        i += 1
                    if turn:
                        numers.append(sign*int(s[j:i]))
                    else:
                        denoms.append(int(s[j:i]))
                    turn = 1 - turn
                    continue
                elif s[i] in "+-":
                    sign = (-1, 1)[s[i] == "+"]
                i += 1
    
            LCM = reduce(lcm, denoms)                       # compute least common multiple for denominators
            numers = [numers[i] * LCM / denoms[i] for i in range(len(numers))]      # adjust numers based on LCM
            numer, denom = sum(numers), LCM
            GCD = gcd(numer, denom)
            return str(numer/GCD) + "/" + str(denom/GCD)
    

  • 0
    L

    Not sure how I feel about that continue
    could turn that elif into

    else:
                    if s[i] in "+-":
                        sign=(-1,1)['+'==s[i]]
                    i+=1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.