Fraction to Recurring Decimal

medium math hash map string

Problem

Given numerator and denominator, return the fraction as a string. If the fractional part is repeating, enclose the repeating block in parentheses.

Inputnumerator = 2, denominator = 3

Output"0.(6)"

Long-divide: 2/3 → integer part 0; remainder 2. Map each remainder to its position in the fractional string. When a remainder repeats, the slice from its first position is the recurring cycle.

numerator

denominator

def fraction_to_decimal(num, den):
    if num == 0: return "0"
    sign = "-" if (num < 0) ^ (den < 0) else ""
    num, den = abs(num), abs(den)
    out = [sign, str(num // den)]
    rem = num % den
    if rem == 0: return "".join(out)
    out.append(".")
    seen = {}
    while rem and rem not in seen:
        seen[rem] = len(out)
        rem *= 10
        out.append(str(rem // den))
        rem %= den
    if rem:
        i = seen[rem]
        out.insert(i, "(")
        out.append(")")
    return "".join(out)

function fractionToDecimal(num, den) {
  if (num === 0) return "0";
  const sign = (num < 0) ^ (den < 0) ? "-" : "";
  num = Math.abs(num); den = Math.abs(den);
  const out = [sign, String(Math.floor(num / den))];
  let rem = num % den;
  if (rem === 0) return out.join("");
  out.push(".");
  const seen = new Map();
  while (rem && !seen.has(rem)) {
    seen.set(rem, out.length);
    rem *= 10;
    out.push(String(Math.floor(rem / den)));
    rem %= den;
  }
  if (rem) {
    out.splice(seen.get(rem), 0, "(");
    out.push(")");
  }
  return out.join("");
}

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        StringBuilder out = new StringBuilder();
        if ((numerator < 0) ^ (denominator < 0)) out.append("-");
        long num = Math.abs((long) numerator), den = Math.abs((long) denominator);
        out.append(num / den);
        long rem = num % den;
        if (rem == 0) return out.toString();
        out.append(".");
        Map<Long, Integer> seen = new HashMap<>();
        while (rem != 0 && !seen.containsKey(rem)) {
            seen.put(rem, out.length());
            rem *= 10;
            out.append(rem / den);
            rem %= den;
        }
        if (rem != 0) {
            out.insert(seen.get(rem), "(");
            out.append(")");
        }
        return out.toString();
    }
}

string fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";
    string out;
    if ((numerator < 0) ^ (denominator < 0)) out += "-";
    long long num = labs((long long) numerator), den = labs((long long) denominator);
    out += to_string(num / den);
    long long rem = num % den;
    if (rem == 0) return out;
    out += ".";
    unordered_map<long long, int> seen;
    while (rem && !seen.count(rem)) {
        seen[rem] = out.size();
        rem *= 10;
        out += to_string(rem / den);
        rem %= den;
    }
    if (rem) {
        out.insert(seen[rem], "(");
        out += ")";
    }
    return out;
}

Explanation

This is just long division done in code, with one extra trick to catch a repeating block: we remember every remainder we have seen and where it landed in the output.

First we handle the sign and the integer part with num // den. If the remainder is already zero, the decimal terminates and we are done. Otherwise we add a . and start generating digits.

Each step mimics grade-school division: multiply the remainder by 10, the next digit is rem*10 // den, and the new remainder is rem*10 % den. Before producing a digit, we record seen[rem] = position. If a remainder ever comes back, the digits since its first appearance form the repeating cycle, so we insert ( at that saved position and append ).

Example: 2/3. Integer part is 0, remainder 2. We do 20 // 3 = 6 with remainder 2 again. Since remainder 2 was already seen at the start of the fractional part, the single digit 6 repeats, giving "0.(6)".

The key insight is that there are only finitely many possible remainders (less than the denominator), so a repeat must happen quickly — which is why the work is bounded by O(d).

Time: O(d) Space: O(d)