# 166. Fraction to Recurring Decimal

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public: string fractionToDecimal(int numerator, int denominator) { if (numerator == 0) return "0"; string ans; if (numerator < 0 ^ denominator < 0) ans += "-"; long n = labs(numerator); long d = labs(denominator); ans += to_string(n / d); if (n % d == 0) return ans; ans += '.'; unordered_map seen; for (long r = n % d; r; r %= d) { if (seen.count(r)) { ans.insert(seen[r], 1, '('); ans += ')'; break; } seen[r] = ans.size(); r *= 10; ans += to_string(r / d); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public String fractionToDecimal(int numerator, int denominator) { if (numerator == 0) return "0"; StringBuilder sb = new StringBuilder(); if (numerator < 0 ^ denominator < 0) sb.append("-"); long n = Math.abs((long) numerator); long d = Math.abs((long) denominator); sb.append(n / d); if (n % d == 0) return sb.toString(); sb.append("."); Map seen = new HashMap<>(); for (long r = n % d; r > 0; r %= d) { if (seen.containsKey(r)) { sb.insert(seen.get(r), "("); sb.append(")"); break; } seen.put(r, sb.length()); r *= 10; sb.append(r / d); } return sb.toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution: def fractionToDecimal(self, numerator: int, denominator: int) -> str: if numerator == 0: return '0' ans = '' if (numerator < 0) ^ (denominator < 0): ans += '-' numerator = abs(numerator) denominator = abs(denominator) ans += str(numerator // denominator) if numerator % denominator == 0: return ans ans += '.' dict = {} remainder = numerator % denominator while remainder: if remainder in dict: ans = ans[:dict[remainder]] + '(' + ans[dict[remainder]:] + ')' break dict[remainder] = len(ans) remainder *= 10 ans += str(remainder // denominator) remainder %= denominator return ans