Fraction to Recurring Decimal — Remainder Tracking HashMap

Problem 190 · Fraction to Recurring Decimal

Difficulty: Medium · Pattern: Remainder Map

Convert numerator/denominator to a decimal string; enclose repeating part in parentheses.

Intuition

Perform long division. Track each remainder and the index where it first appeared. When a remainder repeats, insert parentheses.

Solutions

# Python
def fractionToDecimal(numerator, denominator):
    if numerator == 0: return "0"
    sign = '-' if (numerator < 0) ^ (denominator < 0) else ''
    n, d = abs(numerator), abs(denominator)
    integer = str(n // d)
    remainder = n % d
    if remainder == 0: return sign + integer
    decimal = []
    seen = {}
    while remainder:
        if remainder in seen:
            pos = seen[remainder]
            decimal.insert(pos, '(')
            decimal.append(')')
            break
        seen[remainder] = len(decimal)
        remainder *= 10
        decimal.append(str(remainder // d))
        remainder %= d
    return sign + integer + '.' + ''.join(decimal)

// Java
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), d = Math.abs((long)denominator);
    sb.append(n / d);
    long rem = n % d;
    if (rem == 0) return sb.toString();
    sb.append('.');
    Map<Long,Integer> map = new HashMap<>();
    while (rem != 0) {
        if (map.containsKey(rem)) {
            sb.insert(map.get(rem), '(');
            sb.append(')');
            break;
        }
        map.put(rem, sb.length());
        rem *= 10;
        sb.append(rem / d);
        rem %= d;
    }
    return sb.toString();
}

Complexity

Time: O(d) — at most d distinct remainders
Space: O(d)