Fraction to Recurring Decimal: Long Division with Cycle Detection

Fraction to Recurring Decimal is LeetCode problem 166. Given two integers numerator and denominator, return the fraction as a string. If the fractional part repeats, enclose the repeating portion in parentheses.

Examples:

• 1 / 2 = "0.5"
• 2 / 1 = "2"
• 4 / 333 = "0.(012)"
• 1 / 3 = "0.(3)"

The key insight is that this is long division, the same process you learned in school, and repeating decimals happen when the same remainder appears twice.

Approach: simulate long division, detect cycles with a hash map

Think about what happens when you do long division by hand. You take the remainder, multiply by 10, divide by the denominator, and write down the quotient digit. Then the new remainder becomes the input for the next step. If you ever see a remainder you have seen before, the digits between the two occurrences of that remainder will repeat forever.

The algorithm:

1. Handle the sign. If exactly one of numerator or denominator is negative, prepend "-".
2. Compute the integer part with floor division.
3. If the remainder is zero, return the integer part as a string.
4. Otherwise, start producing decimal digits. Before each digit, record the current remainder and its position in the result string. If the remainder already exists in the map, insert "(" at the stored position and append ")" to the end.
5. For each step: multiply the remainder by 10, compute the next digit (remainder // denominator), and update the remainder (remainder % denominator).
6. If the remainder becomes zero, the decimal terminates.

Python solution

def fractionToDecimal(numerator: int, denominator: int) -> str:
    if numerator == 0:
        return "0"

    result = []

    if (numerator < 0) != (denominator < 0):
        result.append("-")

    num = abs(numerator)
    den = abs(denominator)

    result.append(str(num // den))
    remainder = num % den

    if remainder == 0:
        return "".join(result)

    result.append(".")
    seen = {}

    while remainder != 0:
        if remainder in seen:
            result.insert(seen[remainder], "(")
            result.append(")")
            break
        seen[remainder] = len(result)
        remainder *= 10
        result.append(str(remainder // den))
        remainder %= den

    return "".join(result)

Walkthrough: 4 / 333

Let's trace through the algorithm step by step to see how it produces "0.(012)".

The seen map is the entire mechanism that powers cycle detection here. Each remainder maps to a position in the result list. When a remainder repeats, you know exactly where to insert the opening parenthesis.

Complexity

Time: O(d) where d is the number of distinct decimal digits produced before the result terminates or a cycle is detected. In the worst case, d can be as large as the denominator (since there are at most denominator - 1 distinct nonzero remainders). Each step does constant work.

Space: O(d) for the seen map and the result list, both of which store at most d entries.

Building blocks

This problem decomposes into two reusable pieces you will encounter in other problems.

1. Long division simulation

The core loop of multiplying the remainder by 10, dividing by the denominator, and tracking the new remainder is a direct simulation of manual long division. This same pattern appears anytime you need to produce decimal digits from integer arithmetic without using floating point.

while remainder != 0:
    remainder *= 10
    digit = remainder // denominator
    remainder %= denominator

2. Cycle detection via seen remainders

Storing each remainder with its position and checking for repeats is the same "have I seen this state before?" pattern from Happy Number and Linked List Cycle. The only difference is what you are tracking: here it is a division remainder, there it is a sequence value or a node pointer.

seen = {}
while state is not None:
    if state in seen:
        # cycle detected at seen[state]
        break
    seen[state] = current_position
    state = next_state(state)

On CodeBricks, you drill each building block separately. When they show up combined in a problem like this, you recognize both pieces instantly.

Edge cases

• Zero numerator: 0 / anything = "0". Return immediately.
• Exact division (no repeating part): 1 / 2 = "0.5". The remainder reaches zero and the loop ends naturally, no parentheses needed.
• Negative numbers: -1 / 2 = "-0.5", 1 / -2 = "-0.5", -1 / -2 = "0.5". Use XOR on the signs to decide whether to prepend "-". Work with absolute values after that.
• Large numbers: The denominator determines the maximum cycle length. With denominator = 1,000,000,007, the repeating block could be up to a billion digits. Python handles arbitrary-precision integers natively, but be aware of this in languages with fixed-width types.
• Numerator larger than denominator: 7 / 2 = "3.5". The integer part is nonzero. The algorithm handles this in step 2 without any special case.

From understanding to recall

Reading this walkthrough gives you the logic. But when you face a similar problem in an interview, you need to produce the code from scratch. The two building blocks here, long division simulation and cycle detection with a hash map, appear together in this problem but also separately in many others.

Spaced repetition makes those building blocks automatic. CodeBricks drills you on each piece at increasing intervals. After a few review sessions, "track remainders in a map to find cycles" becomes second nature. You stop thinking about the mechanics and start thinking about the problem.

Related posts

• Happy Number - Cycle detection with a hash set applied to digit-square sequences, the same "have I seen this state?" pattern used here
• Linked List Cycle - Floyd's tortoise and hare for cycle detection in linked lists, another form of the cycle detection building block