Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

In long division, the remainder completely determines the next digit and the next remainder. Reaching zero means the decimal terminates; seeing an earlier remainder means the same sequence of digits must repeat. Remembering where each remainder first appeared tells us exactly where to insert parentheses.

Approach

If the division is exact, return the integer quotient directly, including zero when appropriate.
Otherwise, record a minus sign when the operands have opposite signs, then work with their absolute values. Append the integer part and decimal point.
Before generating each fractional digit, associate the current remainder with the current output position. Multiply it by ten, append the quotient digit, and retain the remainder after division.
Stop on remainder zero. If a remainder is already recorded, insert ( at its saved position and append ). Join the output pieces to produce a finite decimal or the correctly delimited recurring cycle.

class Solution:
    def fractionToDecimal(self, n: int, d: int) -> str:
        if n % d == 0:
            return str(n // d)

        res = []
        if (n > 0 and d < 0) or (n < 0 and d > 0):
            res.append('-')
        n, d = abs(n), abs(d)
        res.append(str(n // d))
        res.append('.')
        rem = n % d
        seen = {}

        while rem != 0:
            if rem in seen:
                res.insert(seen[rem], '(')
                res.append(')')
                break
            seen[rem] = len(res)
            rem *= 10
            res.append(str(rem // d))
            rem %= d

        return "".join(res)

Complexity analysis

Let q be the number of fractional digits produced before the remainder becomes zero or repeats (q ≤ |denominator|). Long division takes O(q) time and O(q) space for the remainder map and output, plus the cost of converting the integer part.