Skip to content

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

    for (long r = n % d; r; r %= d) {
      if (const auto it = seen.find(r); it != seen.cend()) {
        ans.insert(it->second, 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<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();
  }
}

 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