Problem Statement in English

You’re given two integers, numerator and denominator, representing a fraction. Your task is to return the decimal representation of the fraction as a string.

If the decimal representation has a repeating part, enclose the repeating part in parentheses.

Approach

This is an implementation problem. We need to handle both the integer and fractional parts of the division separately.

For the fractional part, we can use a dictionary to keep track of the remainders we encounter. If we see the same remainder again, it means the decimal part is repeating, and we can insert parentheses at the appropriate positions.

Solution in Python


class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if not numerator:
            return "0"
            
        isNeg = (numerator < 0) ^ (denominator < 0)
        sign = "" if not isNeg else "-"
        numerator = abs(numerator)
        denominator = abs(denominator)

        res = [str(numerator // denominator)]
        if not numerator // denominator == numerator / denominator:
            res.append(".")
        numerator %= denominator
        numerator *= 10
        seen = {}

        while numerator:
            if numerator in seen:
                res.insert(seen[numerator], "(")
                res.append(")")
                break
            
            seen[numerator] = len(res)
            res.append(str(numerator // denominator))
            numerator %= denominator
            numerator *= 10

        return (sign + "".join(res))

Complexity

  • Time: $O(n)$
    Here, $n$ is the number of digits in the decimal representation of the fraction.

  • Space: $O(n)$
    We use a dictionary to store the remainders and their positions, which can take up to $O(n)$ space in the worst case.

Mistakes I Made

My first implementation wasn’t as elegant as this one.

And we are done.