Fraction to Recurring Decimal

Fraction to Recurring Decimal

What is this problem about?

The Fraction to Recurring Decimal interview question asks you to convert a given numerator and denominator into its decimal string representation. The catch is that if the fractional part repeats infinitely, you must enclose the repeating sequence in parentheses. For example, 1 / 3 becomes "0.(3)", and 1 / 2 becomes "0.5".

Why is this asked in interviews?

This is a classic Math and Hash Table interview pattern asked by companies like Airbnb, Meta, and Google. It tests your ability to manually simulate long division, a process everyone learns in elementary school but few implement in code. It evaluates your attention to detail regarding edge cases (like zero, negative signs, and integer overflow) and your ability to detect cycles.

Algorithmic pattern used

The solution uses Long Division Simulation combined with a Hash Map.

1. Handle the sign and the integer part first.
2. For the fractional part, keep track of the remainder. Multiply the remainder by 10 and divide by the denominator to get the next digit.
3. Store each unique remainder and its corresponding index in the result string in a Hash Map.
4. If you encounter a remainder that is already in the map, a cycle has started. Insert parentheses using the stored index.

Example explanation

Numerator: 4, Denominator: 33

1. Integer part: $4 / 33 = 0$. Remainder: 4. String so far: "0."
2. Map: {4: 2} (remainder 4 seen at index 2).
3. Next digit: $(4 imes 10) / 33 = 1$. Remainder: $40 - 33 = 7$. String: "0.1"
4. Map: {4: 2, 7: 3}.
5. Next digit: $(7 imes 10) / 33 = 2$. Remainder: $70 - 66 = 4$. String: "0.12"
6. Wait! Remainder 4 is already in the map at index 2.
7. Insert '(' at index 2, and ')' at the end. Final result: "0.(12)".

Common mistakes candidates make

• Integer Overflow: The absolute value of -2^31 (Integer.MIN_VALUE) exceeds the maximum positive 32-bit integer. You must cast the numerator and denominator to 64-bit integers (long) before doing abs().
• Sign Logic: Incorrectly handling the case where only one of the inputs is negative, resulting in a missing or misplaced minus sign.
• Zero Numerator: Not handling $0 / X$ correctly, which should just return "0".

Interview preparation tip

When simulating long division, always map the remainder to the index, not the quotient digit. Different remainders can produce the same quotient digit, but seeing the same remainder guarantees the exact same sequence of calculations will follow.