An one-pass, no-container solution with some math tricks.


  • 0
    M
    from fractions import gcd
    multiplier = 10 # base 10
    def is_in_tail(numerator ,denominator):
        '''
        let q = multiplier = 10
            r = numerator
            N = denominator
        we can see
        r * q^n === r (mod N) [which indicates repeating starts]
        will hold if and only if
            1.  q is prime to N, then we can find 
                some n that q^(n-1) === 1 (mod N) [see to Eular function]
            2.  there exists k|r and k|N and
                (r/k) * q^n === (r/k) (mod (N/k)) satisfies <1.>
        let k = gcd(N,r), we just need to check whether q|(N/r) holds. If not, 
        the repeating part begins.
        '''
        return gcd(denominator//gcd(numerator, denominator), multiplier) == 1
        
    class Solution(object):
        def fractionToDecimal(self, numerator, denominator):
            """
            :type numerator: int
            :type denominator: int
            :rtype: str
            """
            # handle sign
            result = ''
            sign = False
            if(numerator < 0):
                sign = not sign
                numerator = -numerator
            elif(numerator == 0 ):
                return '0'
            if(denominator < 0):
                sign = not sign
                denominator = -denominator
            if sign:
                result += '-'
            result += str(numerator//denominator)
            numerator %= denominator
            if numerator == 0:
                return result
            else:
                result += ('.')
            
            while not is_in_tail(numerator, denominator): # core algorithm
                numerator *= multiplier
                result += str(numerator // denominator)
                numerator %= denominator
                if numerator == 0:
                    return result
            result += ('(')
            
            # the first remained numerator. 
            # If see it again, we reach the end.
            first = numerator
            while True:
                numerator *= multiplier
                result += str(numerator // denominator)
                numerator %= denominator
                if numerator == first:
                    break
            result += (')')
            return result
    

    It can be improved.


Log in to reply
 

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