Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

166. Fraction to Recurring Decimal

Time: $O(n)$

Space: $O(1)$

			


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<int, int> 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;
  }
};




			


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<Long, Integer> 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();
  }
}




			


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