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

• ``````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.

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