Fraction to Recurring Decimal — Simulating Long Division With a Hashmap

Problem Statement#

Given two integers representing the numerator and denominator of a fraction, return the fraction as a string. If the fractional part repeats, enclose the repeating part in parentheses.

Constraints:

• -2^31 <= numerator, denominator <= 2^31 - 1
• denominator != 0
• The answer fits in a 32-bit string-friendly representation.

Input:  numerator = 1, denominator = 2
Output: "0.5"

Input:  numerator = 4, denominator = 333
Output: "0.(012)"

Why This Problem Matters#

LeetCode 166 is a classic hash table FAANG question. Google, Amazon, and Microsoft like it because the algorithm is half math and half data structures. The candidate must remember how long division produces decimal expansions, and recognize that a repeating remainder is exactly what triggers a repeating decimal.

The hashmap interview signal is precise: the data structure tracks remainder -> position in output, so the moment we see a remainder we have already encountered, we know exactly where the repeating block began. That position lets us splice in the parentheses without any post-processing.

The problem is medium-rated because the edge cases (sign handling, integer overflow, integer-only result) catch unprepared candidates more often than the hashmap logic itself.

The Core Insight#

Long division produces digits one at a time. After computing each digit, the next remainder uniquely determines the next digit. If a remainder ever repeats, the decimal expansion from that point is identical to the expansion from its first occurrence, so the digits between the two positions are the repeating block.

Track remainder -> index in result. The moment you re-encounter a remainder, splice ( at that index and append ) at the end.

Visual Dry Run#

1 / 6. Integer part is 0, remainder is 1. Append 0. and continue.

Result: "0.1(6)".

Solution (Optimal)#

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
        sign = "-" if (numerator < 0) ^ (denominator < 0) else ""
        n, d = abs(numerator), abs(denominator)
        integer_part = n // d
        remainder = n % d
        if remainder == 0:
            return sign + str(integer_part)
        result = [sign, str(integer_part), "."]
        seen: dict[int, int] = {}
        while remainder != 0:
            if remainder in seen:
                idx = seen[remainder]
                result.insert(idx, "(")
                result.append(")")
                break
            seen[remainder] = len(result)
            remainder *= 10
            result.append(str(remainder // d))
            remainder %= d
        return "".join(result)

var fractionToDecimal = function(numerator, denominator) {
    if (numerator === 0) return "0";
    const sign = ((numerator < 0) !== (denominator < 0)) ? "-" : "";
    let n = Math.abs(numerator);
    let d = Math.abs(denominator);
    const integerPart = Math.floor(n / d);
    let remainder = n % d;
    if (remainder === 0) return sign + integerPart.toString();
    const result = [sign, integerPart.toString(), "."];
    const seen = new Map();
    while (remainder !== 0) {
        if (seen.has(remainder)) {
            const idx = seen.get(remainder);
            result.splice(idx, 0, "(");
            result.push(")");
            break;
        }
        seen.set(remainder, result.length);
        remainder *= 10;
        result.push(Math.floor(remainder / d).toString());
        remainder = remainder % d;
    }
    return result.join("");
};

Time: O(d) — at most d distinct nonzero remainders before a cycle appears. Space: O(d) — the hashmap can hold up to d - 1 entries.

Common Mistakes#

• Mishandling the sign. numerator * denominator < 0 overflows for INT_MIN; use ^ on the sign bits.
• Forgetting that numerator = 0 should return "0" even when the denominator is negative.
• Returning "0." for whole-number quotients; only append the decimal point when there is a fractional part.
• Tracking the wrong key; the digit can repeat without the decimal repeating, so always key by the remainder.
• Forgetting to splice ( before the digit at the recorded index.

Interview Tips#

• Walk through 1/6 on the whiteboard to ground the algorithm before coding.
• Mention sign handling and integer overflow up front; interviewers expect both at FAANG.
• Use a list/array of strings and join at the end; repeated string concatenation is O(n^2) in some languages.
• Note that the maximum number of distinct remainders is bounded by d, so the loop terminates.

Follow-up Questions#

• What if the input could be very large (BigInteger)? Hint: same algorithm, swap arithmetic for big-int operations.
• What if you must mark the start of the repeat with a different syntax (e.g., bar over digits)? Hint: same hashmap; just change the post-processing.
• Can you compute only whether the fraction terminates? Hint: yes, factor out 2s and 5s from the denominator and check if anything remains.
• What if the numerator and denominator are read as a stream? Hint: precompute integer part lazily, store remainders only when fractional digits are requested.
• How would you do this without a hashmap? Hint: detect cycles with Floyd's algorithm on the remainder sequence.

Key Takeaways#

• LeetCode 166 fuses long-division simulation with hashmap cycle detection.
• Track remainders, not digits, to detect repeats correctly.
• A repeating remainder marks the exact start of the repeating decimal block.
• Time and space are both O(d), the denominator's magnitude.
• Sign handling and integer overflow are the most common interview pitfalls.
• The technique generalizes: any iterative process whose state is finite can be cycle-detected with a hashmap.
• This is a high-signal hashmap interview problem at Google, Amazon, and Microsoft.