Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:


Input: numerator = 1, denominator = 2
Output: "0.5"


Example 2:


Input: numerator = 2, denominator = 1
Output: "2"

Example 3:


Input: numerator = 2, denominator = 3
Output: "0.(6)"

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Mathematics

Starter code: class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        

Solutions:
class Solution:

	def fractionToDecimal(self, numerator, denominator):
		if numerator * denominator < 0:
			add_negative = True
		else:
			add_negative = False
		(numerator, denominator) = (abs(numerator), abs(denominator))
		integer_part = int(numerator // denominator)
		new_numerator = numerator - integer_part * denominator
		dict_residuals = {}
		digit_location = 0
		digit_array = []
		residual = new_numerator
		if residual == 0:
			if add_negative:
				return '-' + str(integer_part)
			else:
				return str(integer_part)
		is_repeating = True
		dict_residuals[residual] = 0
		while True:
			(new_digit, residual) = self.single_digit(residual, denominator)
			digit_location += 1
			if residual == 0:
				dict_residuals[residual] = digit_location
				digit_array.append(str(new_digit))
				is_repeating = False
				break
			elif residual in dict_residuals.keys():
				digit_array.append(str(new_digit))
				is_repeating = True
				break
			else:
				dict_residuals[residual] = digit_location
				digit_array.append(str(new_digit))
		if not is_repeating:
			result = str(integer_part) + '.' + ''.join(digit_array)
		else:
			loc = dict_residuals[residual]
			result = str(integer_part) + '.' + ''.join(digit_array[0:loc]) + '(' + ''.join(digit_array[loc:]) + ')'
		if add_negative:
			return '-' + result
		else:
			return result

	def single_digit(self, value, denominator):
		return (int(10 * value // denominator), 10 * value % denominator)


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		res = ''
		if numerator * denominator < 0:
			res += '-'
		if numerator % denominator == 0:
			return str(numerator // denominator)
		numerator = abs(numerator)
		denominator = abs(denominator)
		res += str(numerator // denominator)
		res += '.'
		numerator %= denominator
		i = len(res)
		table = collections.defaultdict(int)
		while numerator != 0:
			if numerator not in table:
				table[numerator] = i
			else:
				i = table[numerator]
				res = res[:i] + '(' + res[i:] + ')'
				return res
			numerator *= 10
			res += str(numerator // denominator)
			numerator %= denominator
			i += 1
		return res


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		sign = 0
		if numerator * denominator < 0:
			sign = -1
		(numerator, denominator) = (abs(numerator), abs(denominator))
		n = numerator
		s = ''
		if n > denominator:
			s += str(n // denominator)
			n %= denominator
		else:
			s = '0'
		if sign == -1:
			s = '-' + s
		if n == 0:
			return s
		s += '.'
		t = [n]
		x = n
		s1 = ''
		while 1:
			x *= 10
			s1 += str(x // denominator)
			x %= denominator
			if x in t or x == 0:
				break
			else:
				t.append(x)
		if x in t:
			s1 = s1[:t.index(x)] + '(' + s1[t.index(x):] + ')'
		return s + s1


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		sign = '' if not numerator or (numerator < 0) is (denominator < 0) else '-'
		(numerator, denominator) = (abs(numerator), abs(denominator))
		(p, q) = divmod(abs(numerator), abs(denominator))
		(res, decimal, mod, count) = (str(p), [], {q: 0}, 0)
		while q:
			(p, q) = divmod(q * 10, denominator)
			decimal.append(str(p))
			if q in mod:
				idx = mod[q]
				(decimal.insert(idx, '('), decimal.append(')'))
				break
			count += 1
			mod[q] = count
		return sign + res + '.' + ''.join(decimal) if decimal else sign + res


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		prev = []
		prevdigits = []
		s = ''
		if denominator < 0:
			numerator *= -1
			denominator *= -1
		if numerator < 0:
			numerator *= -1
			s += '-'
		(d, numerator) = divmod(numerator, denominator)
		s += str(d)
		if numerator == 0:
			return s
		s += '.'
		while numerator not in prev and numerator != 0:
			prev.append(numerator)
			numerator *= 10
			(d, numerator) = divmod(numerator, denominator)
			prevdigits.append(str(d))
			numerator %= denominator
		if numerator == 0:
			return s + ''.join(prevdigits)
		i = prev.index(numerator)
		return s + ''.join(prevdigits[0:i]) + '(' + ''.join(prevdigits[i:]) + ')'


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		(n, remainder) = divmod(abs(numerator), abs(denominator))
		sign = '-' if numerator * denominator < 0 else ''
		result = [sign + str(n), '.']
		stack = []
		while remainder not in stack:
			stack.append(remainder)
			(n, remainder) = divmod(remainder * 10, abs(denominator))
			result.append(str(n))
		idx = stack.index(remainder)
		result.insert(idx + 2, '(')
		result.append(')')
		return ''.join(result).replace('(0)', '').rstrip('.')


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		sign = '' if numerator * denominator >= 0 else '-'
		(numerator, denominator) = (abs(numerator), abs(denominator))
		(integer, ret) = (str(numerator // denominator), '')
		(remainers, rem) = ({}, numerator % denominator)
		if rem:
			integer += '.'
		while rem and rem not in remainers:
			remainers[rem] = len(ret)
			rem *= 10
			ret += str(rem // denominator)
			rem %= denominator
		if rem:
			ret = ret[:remainers[rem]] + '(' + ret[remainers[rem]:] + ')'
		return sign + integer + ret


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		negative = (numerator < 0) != (denominator < 0)
		numerator = abs(numerator)
		denominator = abs(denominator)
		pre_decimal = numerator // denominator
		remainder = numerator % denominator
		hash_map = {}
		hash_map[remainder] = 0
		post_decimal = []

		def build_fraction(numerator, denominator, post_decimal, depth):
			val = numerator // denominator
			post_decimal.append(val)
			remainder = numerator % denominator
			if remainder in hash_map:
				out = [str(i) for i in post_decimal[:hash_map[remainder]]]
				rep = '('
				rep += ''.join([str(i) for i in post_decimal[hash_map[remainder]:depth]])
				rep += ')'
				rep = '' if rep == '(0)' else rep
				out = ''.join(out)
				return out + rep
			else:
				hash_map[remainder] = depth
			return build_fraction(10 * remainder, denominator, post_decimal, depth + 1)
		suffix = build_fraction(10 * remainder, denominator, post_decimal, 1)
		out = str(pre_decimal) + '.' + suffix
		if out[-1] == '.':
			out = out[:-1]
		out = out if not negative else '-' + out
		return out if out != '-0' else '0'


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		negativeFlag = numerator * denominator < 0
		numerator = abs(numerator)
		denominator = abs(denominator)
		numList = []
		cnt = 0
		loopDict = dict()
		loopStr = None
		while True:
			numList.append(str(numerator // denominator))
			cnt += 1
			numerator = 10 * (numerator % denominator)
			if numerator == 0:
				break
			loc = loopDict.get(numerator)
			if loc:
				loopStr = ''.join(numList[loc:])
				break
			loopDict[numerator] = cnt
		ans = numList[0]
		if len(numList) > 1:
			ans += '.'
		if loopStr:
			ans += ''.join(numList[1:len(numList) - len(loopStr)]) + '(' + loopStr + ')'
		else:
			ans += ''.join(numList[1:])
		if negativeFlag:
			ans = '-' + ans
		return ans


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		st = ''
		if numerator == 0:
			return '0'
		if numerator * denominator < 0:
			st = '-'
		numerator = int(abs(numerator))
		denominator = int(abs(denominator))
		if numerator >= denominator:
			st += str(numerator // denominator)
			numerator %= denominator
		else:
			st += '0'
		position = {}
		fraction = ''
		repeatedPos = -1
		while numerator > 0:
			if numerator in position:
				repeatedPos = position[numerator]
				break
			num = numerator * 10
			val = num // denominator
			position[numerator] = len(fraction)
			fraction += str(val)
			numerator = num % denominator
		if len(fraction) > 0:
			st += '.' + (fraction if repeatedPos == -1 else fraction[:repeatedPos] + '(' + fraction[repeatedPos:] + ')')
		return st


class Solution:

	def fractionToDecimal(self, numerator, denominator):
		if numerator == 0:
			return '0'
		is_neg = (numerator > 0) ^ (denominator > 0)
		numerator = abs(numerator)
		denominator = abs(denominator)
		nd = dict()
		ret = [str(numerator // denominator) + '.']
		while numerator:
			numerator = 10 * (numerator % denominator)
			n_s = str(numerator // denominator)
			if numerator in nd:
				ret.insert(nd[numerator], '(')
				ret.append(')')
				break
			else:
				ret.append(n_s)
			nd[numerator] = len(ret) - 1
		ret = ''.join(ret)
		while ret[-1] == '0':
			ret = ret[:-1]
		if ret[-1] == '.':
			ret = ret[:-1]
		if is_neg:
			ret = '-' + ret
		return ret